The Byteotian University is situated in the city of Byteion. Apart from the main building the university owns n cottages for its academic staff. The cottages are connected with one-way alleys, however, there could be more than one alley between any two cottages (the alley can also form a loop connecting a building to itself). There are also alleys connecting the cottages to the main building. Byteion has been constructed so that no two alleys intersect in a point different from a cottage or the main building (there can however be bridges or tunnels on alleys). Moreover, each and every alley starts and ends in a cottage or the main building. A route exists between each of the cottages and the main building.
Once upon a time, the Byteotian University fancied to hire a well-known computer science pundit - professor Szu. As most outstanding scientists professor Szu has a certain peculiarity to him: each day he wishes to go to the university using a different route (a route being a sequence of alleys, each starting at the cottage the previous one ended at; the main building and each of the cottages may be visited many times). The professor considers two routes distinct if they differ by at least one alley (the order matters; two different alleys connecting the very same two cottages are considered distinct).
Knowing the diagram of connections help the university in finding a cottage which has the greatest number of different routes to the main building possible (staying in such a cottage professor Szu will spend the longest time working at the university). Should there be more than one such cottage - find all of them. Should there be more than 36 500 possible routes between a certain cottage and the main building we will assume that professor Szu can stay in this particular cottage forever (as he surely cannot live infinitely and 100 years seems a safe guess).
For the input data:3 5 1 2 1 3 2 3 3 4 3 4the correct outcome is: 4 1 1 |
|
3 5 1 2 2 3 3 1 3 4 3 4the correct outcome is:
zawsze 3 1 2 3