Se dau n multimi disjuncte, initial fiecare continand un singur element (1, 2, ..., n). Se dau apoi q operatii, fiecare de unul din tipurile: 'UNITE x y' (uneste multimile care contin x si y) sau 'QUERY x y' (verifica daca x si y se afla in aceeasi multime). Procesati operatiile in ordine.
- Date de intrare
- Pe prima linie se citeste n. Pe a doua linie se citeste q. Urmeaza q linii, fiecare de forma '1 x y' (pentru UNITE) sau '2 x y' (pentru QUERY).
- Date de iesire
- Pentru fiecare operatie de tip QUERY (cod 2), se afiseaza 'DA' daca x si y sunt in aceeasi multime, altfel 'NU'.
- Restrictii
- 1 <= n <= 100000, 1 <= q <= 200000
Exemple
Exemplul 1
Intrare
5 5 2 1 2 1 1 2 2 1 2 1 3 4 2 1 3
Iesire
NU DA NU
Exemplul 2
Intrare
1 1 2 1 1
Iesire
DA