홀수 싸이클

무방향 그래프에서 어려운 문제 몇 개는 홀수 싸이클이 없으면 다항 시간에 풀린다. 방향성 그래프에서도 같은 성질이 성립하는지 확인하려면 먼저 방향성 그래프에 홀수 싸이클이 있는지부터 판정해야 한다.

$G$를 자기 루프와 중복 간선이 없는 단순 방향성 그래프라고 하자. 정점 $v$와 $w$가 $G$에 있을 때, $v$에서 $w$로 가는 경로는 정점 열 $(u_1, u_2, \dots, u_l)$이다. 여기서 $u_i$는 서로 다르고, $u_1 = v$, $u_l = w$이며, $1 \le i < l$인 모든 $i$에 대해 $u_i$에서 $u_{i+1}$로 가는 방향성 간선이 있다. $l \ge 2$이고 $u_l$에서 $u_1$로 가는 방향성 간선도 있으면 이 경로를 싸이클이라 하고, $l$을 싸이클의 길이라 한다. 길이가 홀수인 싸이클이 홀수 싸이클이다.

강한 연결 요소는 서로 오갈 수 있는 정점을 모은 극대 집합이다. 모든 싸이클은 하나의 강한 연결 요소 안에 놓인다.

각 테스트케이스마다 그래프에 홀수 싸이클이 있는지 판정하고, 있으면 홀수 싸이클을 품은 강한 연결 요소가 그래프의 어디에 있는지도 정점 번호 하나로 밝힌다.

그림 1. 단순 방향성 그래프

첫 줄에 테스트케이스 수 $T$가 주어진다. ($1 \le T \le 20$)

각 테스트케이스의 첫 줄에는 정점 수 $N$과 간선 수 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 100\,000$, $0 \le M \le 1\,000\,000$) 정점 번호는 $1$부터 $N$까지다.

이어지는 $M$개의 줄에는 간선이 한 줄에 하나씩 v w 형식으로 주어진다. 이는 $v$번 정점에서 $w$번 정점으로 가는 방향성 간선이 있다는 뜻이다. 그래프는 단순 방향성 그래프라서 $v \ne w$이고 같은 간선이 두 번 주어지지 않는다. 다만 $v$에서 $w$로 가는 간선과 $w$에서 $v$로 가는 간선이 함께 주어지는 것은 가능하다.

모든 테스트케이스의 $N$의 합은 $100\,000$ 이하이고, $M$의 합은 $1\,000\,000$ 이하이다.

각 테스트케이스마다 다음을 출력한다.

홀수 싸이클이 없으면 -1을 한 줄에 출력한다.

홀수 싸이클이 있으면 첫 줄에 1을 출력하고, 다음 줄에 홀수 싸이클을 포함하는 강한 연결 요소에 속한 정점 가운데 번호가 가장 작은 것을 출력한다. 그런 강한 연결 요소가 여러 개면 그 모두를 통틀어 가장 작은 정점 번호를 출력한다. 이 정점이 홀수 싸이클 위에 놓일 필요는 없고, 홀수 싸이클을 포함하는 강한 연결 요소에 속하기만 하면 된다.