== code(cpp) |
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(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$.

h2. 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'$.

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

h2. 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 contine $K$ numere naturale in *ordine crescatoare* despartite prin cate un spatiu reprezentand valorile posible pentru *$radacina$*.

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

h2. 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 aceiasi pereche de noduri$
* $Se garanteaza ca intotdeauna exista cel putin o solutie pentru *radacina* $
 

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

h2. Exemplu
table(example). |_. treespotting.in |_. treespotting.out |

| 2 1
1 2
| 2
1 2
|
| 3 3
1 2
2 3
1 3
| 2
1 3
|

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

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

...

== include(page="template/taskfooter" task_id="treespotting") ==