Fişierul intrare/ieşire:treespotting.in, treespotting.outSursăInfoarena Cup 2014
AutorMihai CalanceaAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Treespotting

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

Se da urmatorul pseudocod
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

treespotting.intreespotting.out
2 1
1 2
2
1 2
3 3
1 2
2 3
1 3
2
1 3

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content