Problem

Figure 1. The graphs from the dataset

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

Return: For each graph, output "1" if the graph is acyclic and "-1" otherwise.

See Figure 1 for visual example from the sample dataset.

Sample Dataset

3

2 1
1 2

4 4
4 1
1 2
2 3
3 1

4 3
4 3
3 2
2 1

Sample Output

1 -1 1