Soccer Tactics

Time limit1sMemory limit256 MB

Summary
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 AA to zone BB as an ordered pair (A,B)(A, B). 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 (A,B)(A, B) is a directed edge from AA to BB. A starting zone ss is "suitable" if, starting at ss 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 1111.

Each test case follows. The first line of a test case contains the number of zones NN and the number of prescribed moves MM (1≤N,M≤100 0001 \le N, M \le 100\,000). Each of the next MM lines contains a move (A,B)(A, B), where AA and BB are integers with 0≤A,B<N0 \le A, B < N. The same move may appear more than once, and a move with A=BA = B 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.

Examples1

  1. Example 1

    Input
    2
    4 4
    0 1
    1 2
    2 0
    2 3
    
    4 4
    0 3
    1 0
    2 0
    2 3
    
    Expected output
    0
    1
    2
    
    Confused