eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Дерево

Дерево

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

В упорядкованому кореневому дереві у кожної нелистової вершини визначено порядок синів. Дерева вважаються ізоморфними, якщо при деякому взаємно-однозначному відображенні вершин зберігаються:

  • відношення "вершина s є сином вершини f",

  • порядок синів у кожної вершини.

Задано упорядковане кореневе дерево T та список його модифікацій. Модифікації мають вид: відрізати вершину з заданим номером разом з піддеревом від її поточного батька та додати у якості самого правого сина до деякої вершини.

Потрібно визначити, після якої модифікації дерево вперше стає ізоморфним якомусь з попередніх дерев.

Вхідні дані

У першому рядку вхідного файлу записано два цілих числа: N — кількість вершин у дереві та M — кількість модифікацій (2N100000, 1M100000). Вершини дерева пронумеровано натуральними числами від 1 до N. Корінь дерева має номер 1.

У наступних N рядках записано упоряковані списки синів для вершин заданого дерева. Коженй i-ий список описується кількістю K_i синів i-ої вершини та послідовністю номерів її вершин-синів (0K_iN–1).

У M рядках, що залишились, описано модифікації дерева. Кожна модифікація визначається двома цілими числами S_j та F_j – номером вершини, яку разом з піддеревом відрізають від батька, та номером вершини, до якої її додають у якості самого правого сина (2S_jN, 1F_jN). Гарантується, що вершина F_j не є потомком вершини S_j і не співпадає з нею.

Вихідні дані

Якщо усі M+1 отриманих дерев різні, у вихідний файл необхідно вивести число –1. У протилкжному випадку потрібно вивести через пропуск два цілих числа A та B — номери двох ізоморфних деревьев (0A < BM). Якщо пар ізоморфних дерев декілька, потріно вивести пару з мінімальним номером B.

Дерева нумеруються наступним чином: задане дерево має номер 0. Після j-ої модифікації отримуємо j-те дерево (1jM).

Приклад

Вхідні дані #1
12 15
2 5 2
0
2 11 9
2 8 7
2 3 4
0
0
0
0
0
3 6 12 10
0
3 1
8 2
7 2
6 4
10 4
12 4
9 5
6 8
10 8
12 8
8 5
9 2
4 5
6 9
6 8
Вихідні дані #1
7 13

Примітка

Нижче наведено деякі дерева для першого тесту з умови.

Джерело Очний тур XIII Відкритої Всесибірської олімпіади з програмування імені І.В. Поттосіна