Fişierul intrare/ieşire:	treespotting.in, treespotting.out	Sursă	Infoarena Cup 2014
Autor	Mihai Calancea	Adăugată de	Adrian Budau •freak93
Timp execuţie pe test	0.25 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Treespotting

Fie G = (V, E) un graf cu nodurile din multimea V si muchiile din multimea E.

E' = {}
defineste dfs(nod) ->
   marcheaza ca am trecut prin nod
   pentru vecin al lui nod
      daca nu am mai trecut prin vecin o data
          adauga la E' muchia (nod, vecin)
          dfs(vecin)
dfs(radacina)

Se poate observa usor ca E' contine fix N - 1 muchii si ca G' = (V, E') reprezinta un arbore partial al grafului G. Dandu-se G' si G trebuie sa spuneti pentru ce valori posibile ale lui radacina se putea obtine G' din G.

Date de intrare

Fişierul de intrare treespotting.in va contine pe prima linie 2 numere naturale N si M.
Urmatoarele N - 1 linii vor contine cate 2 numere naturale fiecare, x si y care vor descrie o muchie din E'.
Urmatoarele M - N + 1 linii vor contine cate 2 numere naturale fiecare, x si y care vor descrie o muchie din E\E'.

Date de ieşire

În fişierul de ieşire treespotting.out trebuie sa se afle pe prima linia un numar natural K reprezentand numarul de valori posibila pentru radacina astfel incat sa se poata obtine E' din G aplicand algoritmul descris in pseudocod.
Urmatorul rand trebuie sa contina K numere naturale in ordine crescatoare despartite prin cate un spatiu reprezentand valorile posible pentru radacina.

Restricţii

• 2 ≤ N ≤ 100.000
• N - 1 ≤ M ≤ 150.000
• Pentru 40% din teste N ≤ 3000 si M ≤ 5000
• Pot exista muchii de la nod la el insusi si pot exista si multiple muchii intre aceeasi pereche de noduri
• Se garanteaza ca intotdeauna exista cel putin o solutie pentru radacina

Exemplu

Explicaţie

Pentru primul test indiferent cum fixam radacina obtinem muchia (1, 2).
Pentru cel de-al doilea test daca fixam radacina ca fiind 1 (sau 3) se poate ca vecinul urmator din executia pseudocodului sa fie 2 adaugand muchie (1, 2) (sau (3, 2)) si dupa adaungandu-se si cealalta muchie (3, 2) (sau (1, 2)). Oricum ar decurge algoritmul daca fixam radacina ca fiind 2 nu putem obtine muchiile (1, 2) si (2, 3).

Cum se trimit solutii?