Three Cities#1743
In one state, there are cities. Some cities are connected by roads, and for any two cities and , the following property holds: there is exactly one way to get from city to city if you can only move along roads and are not allowed to pass through the same road more than once.
Recently, the president of this country became interested in the question: which three cities are the most distant from each other? Namely, we define the mutual distance of three cities , , and as the minimum number of roads that should be used to get from to , then from to , and then from to (in this case, it is allowed to use the same road in different journeys).
It is required to find the three cities for which the mutual distance from each other will be maximum.
For example, for five cities connected by roads as shown in Figure 1, the three most distant towns are , , and (the mutual distance is 2 + 3 + 3 = 8), and for the cities in Figure 2, it is any three cities chosen from the set \{1, 2, 4, 5\} (distance 2 + 2 + 2 = 6).
The first line contains the number — the number of cities (3 \leq N \leq 1000). The next lines contain a description of the cities. The description of the -th city first contains K_i — the number of cities to which it is connected by roads (1 \leq K_i \leq N), then K_i numbers — the numbers of the cities with which it is connected.
It is guaranteed that the input data is valid: if there is a road from city to city , then there is a road from city to city , and for all pairs of cities, the property specified in the problem holds.
Output three different numbers — the numbers of the three most distant cities in any order. If there are several solutions, output any of them.
Example 1