Дерево

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

• відношення "вершина 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).

Приклади

Примітка

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