Mucca in pericolo (Gold)

Messa finalmente alle strette, Bessie si è nascosta in una fattoria remota. La fattoria è composta da $n$ granai e n - 1 tunnel bidirezionali tra di essi, e tra ogni coppia di granai esiste un unico percorso. Ogni granaio da cui parte un solo tunnel è un'uscita. Quando arriverà il mattino, Bessie apparirà in superficie in uno dei granai e cercherà di raggiungere un'uscita.

Tuttavia, non appena Bessie uscirà in superficie, le guardie saranno in grado di determinare esattamente la sua posizione. Allora diversi contadini inizieranno a muoversi da vari granai-uscita e cercheranno di catturare Bessie. I contadini si muovono alla stessa velocità di Bessie, ovvero in ogni unità di tempo ciascun contadino può spostarsi da un granaio a quello adiacente. I contadini conoscono in ogni momento la posizione di Bessie, e Bessie conosce in ogni momento la posizione dei contadini. I contadini catturano Bessie se in un qualsiasi momento uno dei contadini si trova nello stesso granaio di Bessie, oppure percorre lo stesso tunnel che sta percorrendo lei. Al contrario, Bessie si salva se riesce a raggiungere un granaio-uscita prima di essere catturata da un qualsiasi contadino.

Bessie non è sicura delle sue possibilità di successo, poiché queste dipendono da quanti contadini le guardie riusciranno a impiegare. È noto che Bessie uscirà in superficie nel granaio $k$. Aiutatela a determinare il numero minimo di contadini necessario per catturarla, supponendo che i contadini si distribuiscano in modo ottimale tra i granai-uscita.