| Fişierul intrare/ieşire: | connectthetree.in, connectthetree.out | Sursă | IIOT 2021-22 Runda 3 |
| Autor | Bogdan Ioan Popa | Adăugată de |  Stefan Dascalescu •stefdascalescu |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Connect the Tree
You are given a tree with N nodes. You should process M queries of two types:
1 x y: (x, y) is an edge from the initial tree. If the edge (x, y) is still in the tree, delete it, else add it back.
2 x y: this output is either 0 or 1. Consider that total is the sum of all the previous type 2 queries. Then compute x_new = (x + total) mod N + 1, y_new = (y + total) mod N + 1.
Output 1 if you can reach y_new from x_new, or 0 if you cannot.
Date de intrare
The first line of the input file connectthetree.in will contain N, M.
On the next N-1 lines you will find the description of the tree. On each line there will be a pair ($x, y$), representing that there will be an edge between x and y.
On the next M lines you will find a triplet ($t, x, y$) representing a query, t is 1 or 2.
Date de ieşire
The output file connectthetree.out will contain as many lines as there are type 2 queries in the input. The ith line will contain the answer for the ith type 2 query.
Restricţii
- 2 ≤ N, M ≤ 2.5 * 10^5
- For tests worth 25 points, 1 ≤ N, M ≤ 1000.
- For tests worth 15 more points, 1 ≤ N ≤ 1000.
Exemplu
| connectthetree.in | connectthetree.out |
|---|---|
| 5 3 1 4 4 2 5 2 3 5 2 1 3 1 2 5 2 1 3 | 1 1 |
