Дерево#4173
В упорядкованому кореневому дереві у кожної нелистової вершини визначено порядок синів. Дерева вважаються ізоморфними, якщо при деякому взаємно-однозначному відображенні вершин зберігаються:
відношення "вершина є сином вершини ",
порядок синів у кожної вершини.
Задано упорядковане кореневе дерево та список його модифікацій. Модифікації мають вид: відрізати вершину з заданим номером разом з піддеревом від її поточного батька та додати у якості самого правого сина до деякої вершини.
Потрібно визначити, після якої модифікації дерево вперше стає ізоморфним якомусь з попередніх дерев.
У першому рядку вхідного файлу записано два цілих числа: — кількість вершин у дереві та — кількість модифікацій (2 \leq N \leq 100000, 1 \leq M \leq 100000). Вершини дерева пронумеровано натуральними числами від до . Корінь дерева має номер .
У наступних рядках записано упорядковані списки синів для вершин заданого дерева. Кожен -ий список описується кількістю K_i синів -ої вершини та послідовністю номерів її вершин-синів (0 \leq K_i \leq N-1).
У рядках, що залишились, описано модифікації дерева. Кожна модифікація визначається двома цілими числами S_j та F_j — номером вершини, яку разом з піддеревом відрізають від батька, та номером вершини, до якої її додають у якості самого правого сина (2 \leq S_j \leq N, 1 \leq F_j \leq N). Гарантується, що вершина F_j не є потомком вершини S_j і не співпадає з нею.
Якщо усі M+1 отриманих дерев різні, у вихідний файл необхідно вивести число . У протилежному випадку потрібно вивести через пропуск два цілих числа та — номери двох ізоморфних дерев (0 \leq A < B \leq M). Якщо пар ізоморфних дерев декілька, потрібно вивести пару з мінімальним номером .
Дерева нумеруються наступним чином: задане дерево має номер . Після -ої модифікації отримуємо -те дерево (1 \leq j \leq M).
Приклад 1
Нижче наведено деякі дерева для першого тесту з умови.
