Državno natjecanje 2020. / Osnovna škola (8. razred) - 3. zadatak

Mirko živi u državi koja ima N gradova označenim brojevima od 1 do N. Gradovi su povezani s N-1 cesti i moguće je jedinstvenim putem doći od nekog grada do bilo kojeg drugog grada.

Jednog sunčanog dana, Mirko odluči posjetiti sve gradove u državi. On može krenuti iz bilo kojeg grada i završiti u bilo kojem gradu, bitno mu je samo da su svaka dva susjedna grada koja posjeti povezana cestom i da barem jednom posjeti svaki grad. Odmah je primjetio da će uz zadane uvjete neke gradove možda posjetiti više puta i to mu ne smeta, ali htio bi minimizirati ukupan broj posjeta gradovima. Tvoj je zadatak ispisati plan Mirkovog putovanja tako da ukupan broj posjeta gradovima bude minimalan

ULAZNI PODACI

U prvom je retku prirodan broj N (1 ≤ N ≤ 100000), broj iz teksta zadatka.

U sljedećih N-1 redova nalaze se po dva prirodna broja A i B (1 ≤ A, B ≤ N, A ≠ B), oznake gradova koji su povezani i-tom cestom.

IZLAZNI PODATCI

U prvi redak ispiši ukupan minimalan broj posjeta gradovima.

U drugi redak ispiši gradove onim redom kojim bi ih Mirko trebao posjećivati.

PROBNI PRIMJERI

Ulaz

5
1 2
2 3
3 4
4 5

Izlaz

5
1 2 3 4 5

Ulaz

10
1 2
2 4
5 2
6 3
3 1
6 7
9 7
8 6
8 10

Izlaz

15
10 8 6 7 9 7 6 3 1 2 5 2 4 2 1

Ulaz

6
3 1
3 5
4 3
4 2
2 6

Izlaz

7
1 1 1 1 1 1 1

Objašnjenje

Opis prvog primjera:

Za ovakav izlaz na tom primjeru dobio bi sve bodove.

Opis drugog primjera:

Za ovakav izlaz na tom primjeru dobio bi 0,21*B bodova.

Opis trećeg probnog primjera:

Za ovakav izlaz na tom primjeru dobio bi 0,6*B bodova.