drumuri

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).

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).

Date de intrare

Fişierul de intrare drumuri.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.

Date de ieşire

Fişierul de ieşire drumuri.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.

Restricţii şi precizări

• 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.

Exemplu

drumuri.in

6 14
1 2 4
1 6 5
4 1
1 1 5
1 1 6
4 5
3 6 1
4 4
4 3
3 3 1
3 3 0
2 3 2
2 5 6
3 6 1

drumuri.out

1
1
1 1
1
0
2 1 6
1 5
2 2 4
1 3
0
1 3
0
1
0

Explicaţii

Graful are N=6 noduri şi se dau M=14 operaţii:

1. Se adaugă muchie între nodurile 2 şi 4 cu succes.
2. Se adaugă muchie între nodurile 6 şi 5 cu succes.
3. Nodul 1 face parte dintr-un drum cu un singur nod: 1.
4. Se adaugă muchie între nodurile 1 şi 5 cu succes.
5. Adăugarea muchiei între nodurile 1 şi 6 eşuează, deoarece s-ar forma un ciclu în graf.
6. Nodul 5 face parte dintr-un drum cu 2 capete: 1 şi 6.
7. Există un singur nod la distanţă 1 de nodul 6: nodul 5.
8. Nodul 4 face parte dintr-un drum cu 2 capete: 2 şi 4.
9. Nodul 3 face parte dintr-un drum cu un singur nod: 3.
10. Există zero noduri la distanţă 1 de nodul 3.
11. Există un singur nod la distanţă 0 de nodul 3: nodul 3.
12. Ştergerea muchiei dintre nodurile 3 şi 2 eşuează, deoarece această muchie nu există.
13. Ştergerea muchiei dintre nodurile 5 şi 6 se efectuează cu succes.
14. Există zero noduri la distanţă 1 de nodul 6.