Problem

Given: A positive integer $k \le 20$ and $k$ simple directed graphs with at most $10^3$ vertices and $2 \cdot 10^3$ edges each in the edge list format.

Return: For each graph, output a vertex from which all other vertices are reachable (if such a vertex exists) and "-1" otherwise.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

Sample Dataset

2

3 2
3 2
2 1

3 2
3 2
1 2

Sample Output

3 -1