== include(page="template/taskheader" task_id="inghetare") ==

În Tărâmul Ooo există $n$ aşezări, legate între ele prin $n-1$ poteci astfel încât se poate ajunge de la orice aşezare la oricare alta folosind doar potecile respective.

În Tărâmul Ooo există $n$ aşezări, legate între ele prin $n - 1$ poteci astfel încât se poate ajunge de la orice aşezare la oricare alta folosind doar potecile respective.

Regele Gheţii, supărat că Finn şi Jake îl tot înfrâng, vrea să aducă haos în ţinut. Planul lui este simplu: va distruge potecile una câte una. În fiecare secundă, el alege aleatoriu o potecă neîngheţată şi creează pe ea un strat gros de gheaţă, astfel blocând-o. Regele se declară mulţumit doar în momentul în care nu mai există vreo aşezare cu $3$ sau mai multe poteci neîngheţate care o leagă de alte aşezări.

h2. Restricţii

* $1 \leq n \leq 2000$
* $1 \leq u, v \leq n$
* graful descris este un arbore (conex, fără cicluri)

* $1 ≤ n ≤ 2000$
* $1 ≤ u, v ≤ n$

Subtaskuri:

1. ($3$ puncte) $n \leq 12$
2. ($12$ puncte) există exact un nod cu grad strict mai mare decât $2$
3. ($35$ puncte) $n \leq 300$
4. ($50$ puncte) $n \leq 2000$

 
|_. #  |_. Punctaj |_. Restricţii |
| 1 | 3 | $n ≤ 10$ |
| 2 | 12| Există exact $1$ aşezare cu strict mai mult de $2$ poteci conectate la ea |
| 3 | 35 | $n ≤ 300$ |
| 4 | 50 | Fără alte restricţii |

h2. Exemplu