Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

2189.   The Key Stations
Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 1276   Accepted Runs: 437    Multiple test files

In the city named ACM, there aren't any network stations by now, what's a pity! So the government plans to establish a complete network, and decides to set up a team in charge of this project.

There are totally N districts. And the team plans to build one network station in each district. Also in order to make sure the communication of the city, there exists at least one path between any two stations, directly or indirectly. For the sack of safety, they hire some engineers working in stations so that if there are any problems they can fix them in no time. Considering the cost, they don't want to hire enough engineers for each station, instead only for the key stations. The key station is the one that if it halts down, the network left isn't connected any more. For example, in the graph given, station 1 is a key station, while the others are not.

So the problem is how to find all of the key stations in the city. The leader of the team, Jack, needs help! As a program expert, can you help him?


The input consists of several blocks of lines. Each block describes one network. In the first line of each block there is the number of districts N ≤ 1000. Each of the next at most N lines contains the number of a station followed by the numbers of some stations to which there is a direct connection from this station.

These at most N lines completely describe the network, i.e., each direct connection of two stations in the network is contained at least in one row. All numbers in one line are separated by one space. Each block ends with a line containing just 0. The last block has only one line with N = 0.


For each block, first output the number of the key stations m, then m ascending numbers are followed. The numbers are separated by exactly one blank.

Sample Input

1 5 2 4 3
4 3
5 2
1 2 3 4 5
3 2
4 3
5 2

Sample Output

1 1

Author: Kandy

Source: TOJ 2006 Weekly Contest 3
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:G.D.Retop. Developer: SuperHacker, G.D.Retop