== include(page="template/taskheader" task_id="disconnect") ==

Poveste şi cerinţă...

Fie $T$ un arbore neorientat cu $N$ noduri. Vom aplica asupra lui $M$ operaţii de tipul:
 
$1 x y$  Se şterge muchia $x-y$ din arbore.
$2 x y$  Se pune întrebarea "Există drum in arbore de la nodul $x$ la nodul $y$?"
 
Cerinţa este ca programul vostru să afişeze răspunsul corect pentru toate operaţiile de tip $2$.

h2. Date de intrare

Fişierul de intrare $disconnect.in$ va conţine pe prima linie numerele $N$ şi $M$, semnificând numărul de noduri, respectiv numărul de operaţii care se vor efectua asupra arborelui. Următoarele $N - 1$ linii conţin câte o pereche de numere $X Y$, semnificând faptul că există o muchie neorientată între nodurile $X$ şi $Y$. Următoarele $M$ linii conţin câte trei numere $tip X Y$. Numărul $tip$ denotă tipul operaţiei, fiind egal cu $1$ dacă este vorba de o ştergere sau $2$ dacă e vorba de o întrebare. Numerele $X$ şi $Y$ vor fi folosite pentru a genera nodurile pe care se va aplica operaţia respectivă. Mai exact, aceste noduri vor fi $A = X xor V$ şi $B = X xor V$ unde $V$ este o variabila iniţial egală cu $0$. După fiecare operaţie de tip $2$ variabila $V$ îşi va schimba valoarea în funcţie de răspunsul afişat. Vă oferim un fragment de cod în $C++$ care generează şi rezolvă operaţiile.

Fişierul de intrare $disconnect.in$ va conţine pe prima linie numerele $N$ şi $M$, semnificând numărul de noduri, respectiv numărul de operaţii care se vor efectua asupra arborelui. Următoarele $N - 1$ linii conţin câte o pereche de numere $X Y$, semnificând faptul că există o muchie neorientată între nodurile $X$ şi $Y$. Următoarele $M$ linii conţin câte trei numere $tip X Y$. Numărul $tip$ denotă tipul operaţiei, fiind egal cu $1$ dacă este vorba de o ştergere sau $2$ dacă e vorba de o întrebare. Numerele $X$ şi $Y$ vor fi folosite pentru a genera nodurile pe care se va aplica operaţia respectivă. Mai exact, aceste noduri vor fi $A = X xor V$ şi $B = X xor V$ unde $V$ este o variabila iniţial egală cu $0$. După fiecare operaţie de tip $2$ variabila $V$ îşi va schimba valoarea în $A$ (dacă răspunsul la întrebare a fost pozitiv), respectiv în $B$ (dacă acesta a fost negativ). Vă oferim un fragment de cod în $C++$ care generează şi rezolvă operaţiile.

==code(C) |

    int XOR = 0;

    int V = 0;

    for (int i = 0; i < M; ++i) {
        int type, x, y; cin >> type >> x >> y;

        x ^= XOR;
        y ^= XOR;

        int a = x xor V;
        int b = y xor V;

        if (type == 1) {

            T.removeEdge(x, y);

            removeEdge(a, b);

        } else

            if (T.query(x, y)) {

            if (query(a, b)) {

                cout << "YES\n";

                XOR = x;

                V = a;

            } else {
                cout << "NO\n";

                XOR = y;

                V = b;

            }
    }

h2. Date de ieşire

În fişierul de ieşire $disconnect.out$ ...

Fişierul de ieşire $disconnect.out$ va conţine câte o linie pentru fiecare operaţie de tip $2$. Linia va conţine $YES$ dacă răspunsul este pozitiv şi $NO$ altfel.

h2. Restricţii

h2. Restricţii şi precizări

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 500 000$
* Pentru $20%$ din punctaj testele respectă restricţia $1 ≤ N ≤ 1 000$, $1 ≤ M ≤ 5 000$
* Pentru $40%$ din punctaj testele respectă restricţia $1 ≤ N ≤ 10 000$, $1 ≤ M ≤ 500 000$
* Operaţia $xor$ poate fi implementată prin operatorul "^" sau "xor" în C/C++ şi operatorul "xor" în Pascal.

h2. Exemplu
table(example). |_. disconnect.in |_. disconnect.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6 7
1 2
1 3
1 4
4 5
4 6
2 2 5
1 3 6
2 0 7
2 7 6
2 7 4
1 4 7
2 6 7
| YES
NO
YES
YES
NO

|
h3. Explicaţie

...

Odată generate operaţiile ar arăta în felul următor:
2 2 5
1 1 4
2 2 5
2 2 3
2 5 6
1 1 2
2 3 2
 

== include(page="template/taskfooter" task_id="disconnect") ==