Mucca a piede libero (Platino)#10427
Messa finalmente alle strette, Bessie si è rintanata in una fattoria isolata. La fattoria è composta da fienili e n - 1 tunnel bidirezionali che li collegano, in modo tale che tra ogni coppia di fienili esista un unico percorso. Ogni fienile da cui parte un solo tunnel è un'uscita. Quando arriverà il mattino, Bessie riemergerà in uno dei fienili e cercherà di raggiungere un'uscita.
Tuttavia, nel momento in cui Bessie riemergerà in un fienile, le forze dell'ordine saranno in grado di individuarne con precisione la posizione. Alcuni contadini partiranno allora da diversi fienili d'uscita e cercheranno di catturarla. I contadini si muovono alla stessa velocità di Bessie, quindi a ogni unità di tempo ciascun contadino può spostarsi da un fienile a uno adiacente. I contadini sanno in ogni momento dove si trova Bessie, e Bessie sa in ogni momento dove si trovano i contadini. I contadini catturano Bessie se in un qualsiasi istante un contadino si trova nello stesso fienile di Bessie oppure sta attraversando il suo stesso tunnel. Al contrario, Bessie riesce a fuggire se raggiunge un fienile d'uscita strettamente prima che un qualsiasi contadino la catturi.
Bessie non sa in quale fienile riemergere. Per ciascuno degli fienili, aiutala a determinare il numero minimo di contadini necessari per catturarla se riemergesse lì, supponendo che i contadini si posizionino in modo ottimale tra i fienili d'uscita.
La prima riga contiene un intero n~(2 \le n \le 7 \cdot 10^4). Ciascuna delle successive n - 1 righe contiene due interi a_i e b_i~(1 \le a_i, b_i \le n), che descrivono un tunnel tra i fienili a_i e b_i.
Stampa righe. La -esima riga deve contenere il numero minimo di contadini necessari per catturare Bessie se riemerge nel fienile .
Esempio 1