Дерево
В упорядоченном корневом дереве у каждой нелистовой вершины определён порядок сыновей. Деревья считаются изоморфными, если при некотором взаимно-однозначном отображении вершин сохраняются:
отношение "вершина s является сыном вершины f",
порядок сыновей у каждой вершины.
Дано упорядоченное корневое дерево T и список его модификаций. Модификации имеют вид: отрезать вершину с заданным номером вместе с поддеревом от её текущего отца и добавить в качестве самого правого сына к некоторой вершине.
Требуется определить, после какой модификации дерево впервые становится изоморфным какому-то из предыдущих деревьев.
Входные данные
В первой строке входного файла записано два целых числа: N — количество вершин в дереве и M — количество модификаций (2 ≤ N ≤ 100000, 1 ≤ M ≤ 100000). Вершины дерева пронумерованы натуральными числами от 1 до N. Корень дерева имеет номер 1.
В следующих N строках записаны упорядоченные списки сыновей для вершин исходного дерева. Каждый i-ый список описывается количеством K_i сыновей i-ой вершины и последовательностью номеров её вершин-сыновей (0≤ K_i ≤ N–1).
В оставшихся M строках описаны модификации дерева. Каждая модификация определяется двумя целыми числами S_j и F_j – номером вершины, которую вместе с поддеревом отрезают от отца, и номером вершины, к которой её добавляют в качестве самого правого сына (2 ≤ S_j ≤ N, 1 ≤ F_j ≤ N). Гарантируется, что вершина F_j не является потомком вершины S_j и не совпадает с ней.
Выходные данные
Если все M+1 получающихся деревьев различны, в выходной файл необходимо вывести число –1. В противном случае нужно вывести через пробел два целых числа A и B — номера двух изоморфных деревьев (0 ≤ A < B ≤ M). Если пар изоморфных деревьев несколько, требуется вывести пару с минимальным номером B.
Деревья нумеруются следующим образом: исходное дерево имеет номер 0. После j-ой модификации получаетсяj-ое дерево (1 ≤ j ≤ M).
Комментарий
Ниже приведены некоторые деревья для первого теста из условия.
