---
# System prepended metadata

title: Cepivo

---

# Cepivo

Končno smo dobili cepivo s perfektno učinkovitostjo, ki ga  moramo razvoziti med $N$ mest. Slučajno se je izkazalo, da je teh $N$ mest povezanih z $N-1$ letalskimi povezavami (ena letalska povezava povezuje dve mesti), tako da mesta in povezave tvorijo drevo.

Cepivo lahko razvozimo tako, da izberemo mesti $a$ in $b$. Cepivo lahko dostavimo v vsa mesta, ki so na poti med vključno mestoma $a$ in $b$.

Poišči minimalno število letal, ki jih potrebujemo za transport cepiva in izpiši pare mest med katerimi naj pošljemo letala. Eno letalo lahko leti med več mesti, če sta mesti povezani z letalsko povezavo.

## Vhod

V prvi vrstici standardnega vhoda se nahaja naravno število $N$ - število mest.

V naslednjih $N-1$ vrsticah se nahaja par celih števil $a$ in $b$, ki označuje, da sta mesti $a$ in $b$ povezani.

## Izhod

Na standardni izhod izpiši najmanjše število transportnih letal, potrebnih za razvoz cepiva. In pare mest, kjer letala začnejo in končajo svoj polet. izpiši katerokoli rešitev.

## Primer

### Vhod

```
5
1 3
1 4
2 3
3 5
```

### Izhod

```
2
1 4
2 5
```

### Komentar

V tem primeru lahko pošljemo dve letali s cepivom. Prvo začne v mestu $1$ in konča v mestu $4$, drugo začne v mestu $2$, obišče mesto $3$ in konča v mestu $5$.

## Podnaloge

1. podnaloga (20 točk): $n \leq 20$
2. podnaloga (35 točk): $n \leq 5000$
3. podnaloga (45 točk): $n \leq 200000$

## Opomba

Lahko obstaja več načinov kako razvoziti cepivo po svetu. Izpiši kateregakoli.