Rezolvare PBinfo #3339

Se consideră un graf cu N noduri numerotate de la 1 la N și M operații de trei tipuri:

• 1 x y – se adaugă în graf muchia (x, y). Dacă muchia există deja, operația nu se efectuează
• 2 x y – întrebare: nodurile x și y se află sau nu în aceeași componentă conexă?
• 3 – întrebare: care este numărul maxim de noduri dintr-o componentă conexă?

Cerința

Trebuie să răspundeți la toate întrebările de tip 2 și 3.

Date de intrare

Programul citește de la tastatură numerele N și M, iar pe următoarele M linii se află operațiile date fie prin trei valori de forma op x y (pentru operațiile de tip 1 și 2), fie printr-o singură valoare 3 (pentru operațiile de tip 3).

Date de ieșire

Programul va afișa pe ecran, pe câte o linie, răspunsul la fiecare întrebare de tip 2 și 3. Dacă la o întrebare 2 x y răspunsul este afirmativ, adică x și y se află în aceeași componentă conexă, atunci veți afișa DA, iar în caz contrar veți afișa NU.

Restricții și precizări

• 3 ≤ N ≤ 32.000
• 3 ≤ M ≤ 300.000
• va exista cel puțin o operație de fiecare tip.

Exemplu:

Intrare

6 6
1 1 4
1 3 6
2 4 6
1 1 3
2 4 6
3

Ieșire

NU
DA
4

Explicație

Sunt 6 noduri și 6 operații. După primele două operații, nodurile 1 și 4 sunt în aceeași componentă conexă și 3 și 6 sunt în aceeași componentă conexă. La întrebarea 2 4 6 răspunsul este evident NU. La a patra operație 1 și 3 sunt trecute în aceeași componentă conexă, deci va exista o componentă conexă cu 4 noduri: {1,3,4,6}, deci la întrebarea 2 4 6 răspunsul este DA, iar la ultima operație de tip 3 răspunsul este 4 (componenta conexă maximală are patru noduri).