In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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:
Task author: Pawel Parys.