Условие

---

Е. КОРЕНОВО ДЪРВО
---
Всяко дърво (т.е. свързан граф без цикли) можем да превърнем в кореново дърво, като изберем един от върховете, да го означим с r, за корен. Добре известно е, че всеки два върха на дърво са свързани с единствен път и броя на ребрата по този път наричаме разстояние между двата върха.  Ако върхът u е на разстояние d от r, върхът v е на разстояние d + k от r, k > 0, и u е на пътя от r до v,  тогава u се нарича k-ти предшественик на v, а v – наследник на u. Върховете, които нямат наследници, се наричат листа на кореновото дърво. Напишете програма, която по зададено кореново дърво изпълнява следните заявки:
- 0 x y – добавя в дървото нов лист x, като го свързва с ребро към y;
- 1 x – премахва листа x от дървото;
- 2 x k – запитване за k-тия предшественик на x.

Вход: 
Програмата трябва да може да обработва няколко примера при едно изпълнение. На първия ред на стандартния вход ще бъде зададен броят T на тестовите примери. Първият ред на всеки от тях ще съдържа броя N на върховете на зададеното кореново дърво  и броя Q на заявките. Следват N реда с по две числа x  и y, указващи че x e пряк наследник (дете) на y. Когато у е 0, това означава, че x e корен на дървото (т.е няма баща). Следват Q реда, съдържащи по един от трите типа заявки, споменати по-горе.

Изход: 
За всяка заявка от тип 2, програмата трябва да изведе на стандартния изход k-тия предшественик на x. Ако такъв предшественик не съществува или в дървотоняма връх x, тогава програмата трябва да изведе 0.

Ограничения: 
1 ≤ N ≤ 10^5, 1 ≤ Q ≤ 10^5, 1 ≤ x ≤ 10^5, 0 ≤ y < 10^5, 1 ≤ k ≤ 10^5.

Примерен вход:
1
8 11
4 0
1 4
7 1
3 2
2 4
9 1
6 2
124 9
2 124 3
1 124
2 124 3
0 55 7
0 8 55
0 10 8
2 10 4
2 6 1
2 3 2
2 9 7
2 8 3	

Примерен изход:
4
0
1
2
4
0
1