W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
There is a cave in Byteotia. It consists of chambers and corridors connecting them. The corridors are arranged in such way, that there is a unique path between each pair of chambers. In one of these chambers Hansel has hidden a treasure, but he won't tell which one it is. Gretel desires to know it. So she asks Hansel about various chambers. When she guesses right Hansel tells her she is right, and when she guesses wrong he tells her which way from this chamber leads to the treasure.
Write a programme that:
In the first line of the standard input there is one positive integer , . It is the number of chambers in the cave. The chambers are numbered from to . In the following lines the corridors linking the chambers are described, one per line. Each of these lines contains a pair of distinct positive integers and (), separated by a single space. It indicates that there is a corridor between chambers and .
Your programme should write one integer in the standard output, the minimal number of questions Gretel has to ask in the worst case (i.e. we assume Gretel asks the questions in the best possible way, but the treasure is hidden in the chamber that requires the largest number of questions).
For the input data:
5 1 2 2 3 4 3 5 3
the correct result is:
2
Task author: Pawel Parys.