Soccer Tactics
Time limit1sMemory limit256 MB
Given a directed graph, find every vertex from which all other vertices are reachable, or report that none exists.
- Level
Medium6 of 10
- Topics
- Graph, DFS, Topological sort, Implementation
- Solved
- No attempts yet
Problem
The World Cup is coming! Coach Dohyun, famous for devising ingenious tactics, is preparing thoroughly for his team to win. His strategy divides the field into several zones and describes a move that takes a player from zone to zone as an ordered pair . Dohyun is convinced that if every player on his team travels using only these moves, the team will surely win.
Dohyun told his players to find one starting zone from which, following only the prescribed moves, they can reach every other zone, and to set off from there. But he forgot that his players are not as clever as he is, and they find it hard to locate such a starting zone. Now you must find it for them.
The moves can be viewed as a directed graph: the zones are the vertices and each move is a directed edge from to . A starting zone is "suitable" if, starting at and following only the prescribed moves (each move may be used any number of times), a player can reach every other zone. For each test case, find all suitable starting zones.
Input
The first line contains the number of test cases, an integer not greater than .
Each test case follows. The first line of a test case contains the number of zones and the number of prescribed moves (). Each of the next lines contains a move , where and are integers with . The same move may appear more than once, and a move with is allowed.
Each test case is separated by a single blank line.
Output
For each test case, print all suitable starting zones in ascending order, one per line. If there is no such starting zone, print Confused.
Separate the outputs of consecutive test cases with one blank line.