Odd Cycle in a Directed Graph

Some problems that are hard on a general undirected graph become solvable in polynomial time once the graph has no odd cycle. To find out whether the same holds for directed graphs, you first have to decide whether a directed graph contains an odd cycle.

Let $G$ be a simple directed graph with no self loops and no duplicate edges. For vertices $v$ and $w$ of $G$, a path from $v$ to $w$ is a sequence of vertices $(u_1, u_2, \dots, u_l)$ where the $u_i$ are pairwise distinct, $u_1 = v$, $u_l = w$, and for every $i$ with $1 \le i < l$ there is a directed edge from $u_i$ to $u_{i+1}$. If $l \ge 2$ and there is also a directed edge from $u_l$ to $u_1$, the path is a cycle and $l$ is its length. A cycle of odd length is an odd cycle.

A strongly connected component is a maximal set of vertices that can all reach each other. Every cycle lies inside a single strongly connected component.

For each test case, decide whether the graph contains an odd cycle. If it does, also report where such a cycle sits by naming one vertex number of the strongly connected component that holds it.

Figure 1. Simple directed graphs

The first line contains the number of test cases $T$. ($1 \le T \le 20$)

The first line of each test case contains the number of vertices $N$ and the number of edges $M$, separated by a space. ($1 \le N \le 100\,000$, $0 \le M \le 1\,000\,000$) Vertices are numbered from $1$ to $N$.

Each of the next $M$ lines contains one edge in the form v w, meaning there is a directed edge from vertex $v$ to vertex $w$. The graph is a simple directed graph, so $v \ne w$ and no edge is given twice. An edge from $v$ to $w$ and an edge from $w$ to $v$ may both appear.

The sum of $N$ over all test cases is at most $100\,000$, and the sum of $M$ over all test cases is at most $1\,000\,000$.

Print the following for each test case.

If the graph has no odd cycle, print -1 on one line.

If the graph has an odd cycle, print 1 on the first line, then on the next line print the smallest vertex number among the vertices that belong to a strongly connected component containing an odd cycle. If several such components exist, print the smallest vertex number over all of them. That vertex does not have to lie on an odd cycle itself; it only has to belong to a strongly connected component that contains one.