Fişierul intrare/ieşire:connectthetree.in, connectthetree.outSursăIIOT 2021-22 Runda 3
AutorBogdan Ioan PopaAdăugată destefdascalescuStefan Dascalescu stefdascalescu
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.inconnectthetree.out
5 3
1 4
4 2
5 2
3 5
2 1 3
1 2 5
2 1 3
1
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?