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

Poveste şi cerinţă...

p<>. Se consideră un graf neorientat având iniţial $N$ noduri izolate numerotate de la $1$ la $N$ (deci graful are iniţial $0$ muchii). Asupra acestui graf se pot efectua $4$ tipuri de operaţii, precum adăugarea unei muchii noi, ştergerea unei muchii şi două tipuri de interogări. Există însă o constrângere: la orice moment de timp, componentele conexe ale grafului trebuie să aibă structura unui drum (adică fiecare nod are cel mult $2$ vecini şi graful nu conţine cicluri). Cele $4$ tipuri de operaţii sunt următoarele:
 
* {*Tipul 1*}: Adaugă o muchie între nodurile $i$ şi $j$. Această operaţie se efectuează cu succes dacă nu încalcă constrâgerea. În caz contrar, operaţia nu va fi efectuată.
* {*Tipul 2*}: Elimină muchia dintre nodurile $i$ şi $j$. Această operaţie se efectuează cu succes dacă există muchie între nodurile $i$ şi $j$.
* {*Tipul 3*}: Determină toate nodurile aflate la distanţă $D$ de nodul $i$. Distanţa dintre două noduri este egală cu numărul minim de muchii al unui drum în graf ce uneşte cele două noduri. Din cauza constrângerii, pot exista cel mult două noduri la distanţă $D$ faţă de un alt nod.
* {*Tipul 4*}: Determină nodurile-capăt ale drumului (componentei conexe) din care face parte nodul $i$ $(i$ ar putea fi chiar unul din capete sau singurul capăt, dacă el este un nod izolat).
 
h2. Cerinţă
 
Dându-se o secvenţă de $M$ operaţii şi pornind de la un graf fără nicio muchie, afişaţi rezultatul fiecărei operaţii din secvenţă (în ordinea în care acestea sunt date).

h2. Date de intrare

Fişierul de intrare $drumuri4.in$ ...

Fişierul de intrare $drumuri4.in$ conţine:
 
* Pe prima linie numerele $N$ şi $M$ separate, printr-un spaţiu.
* Pe fiecare din următoarele $M$ linii este descrisă o operaţie, printr-o succesiune de numere întregi separate prin spaţii. Primul număr de pe linie reprezintă tipul operaţiei (de la $1$ la $4$).
** Dacă operaţia este de tipul $1$, atunci urmează două numere întregi $i$ şi $j$, având semnificaţia că se va adăuga o muchie între nodurile $i$ şi $j$ din graf (dacă nu se încalcă constrângerea).
** Dacă operaţia este de tipul $2$, atunci urmează două numere întregi $i$ şi $j$, având semnificaţia că se va şterge muchia dintre nodurile $i$ şi $j$ din graf (dacă există).
** Dacă operaţia este de tipul $3$, atunci urmează două numere întregi $i$ şi $D$, având semnificaţia că se doreşte determinarea tuturor nodurilor aflate la distanţă exact $D$ de nodul $i$.
** Dacă operaţia este de tipul $4$, atunci urmează un singur număr întreg $i$, având semnificaţia că dorim să determinăm capetele drumului din care face parte nodul $i$.

h2. Date de ieşire

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

p<>. Fişierul de ieşire $drumuri4.out$ va conţine $M$ linii. A $i$-a linie va conţine rezultatul celei de-a $i$-a operaţii din fişierul de intrare. Dacă operaţia este de tipul $1$ sau $2$, rezultatul său este $1$, dacă operaţia s-a efectuat cu succes, sau $0$, în caz contrar. În cazul operaţiilor de tipul $3$ şi $4$, rezultatul constă dintr-o mulţime de noduri. Afişaţi mai întâi numărul de noduri din mulţime, apoi, pe aceeaşi linie, elementele mulţimii în ordine crescătoare.

h2. Restricţii

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

* $1 ≤ N ≤ 40 000$
* $1 ≤ M ≤ 400 000$
* $0 ≤ D ≤ N - 1$
* $1 ≤ i, j ≤ N$
* Nu se vor adăuga muchii de la un nod la el însuşi.
* Pentru $40%$ din teste $N ≤ 5000$ şi $M ≤ 20 000$.
 

h2. Exemplu