문제
방향 그래프가 주어지면 그래프에 홀수 크기 단순 싸이클이 있는지 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에 정점 개수 N과 간선 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000) 다음 M줄에는 각 간선의 시작점, 끝점의 번호가 주어진다. 노드의 번호는 1 이상 N 이하의 정수이다. 그래프에 중복 간선과 자기 루프는 없다.
출력
만약 홀수 싸이클이 없다면 -1만 출력한다.
만약 홀수 싸이클이 있다면 첫 번째 줄에는 1을, 두 번째 줄에는 싸이클의 크기를, 세 번째 줄부터 한 줄에 하나씩 싸이클에 포함되는 정점의 번호를 출력한다. 답이 여러 개이면 아무거나 출력해도 되나 싸이클에 포함된 모든 정점의 번호는 서로 달라야 함에 유의하여라.
예제 #1
3 3
2 3
2 1
1 3
-1
예제 #2
3 4
2 3
3 2
1 2
1 3
-1
예제 #3
3 4
2 1
2 3
1 3
3 2
1
3
2
1
3
예제 #4
8 9
1 2
2 3
3 4
4 1
5 6
6 7
7 8
8 5
5 8
-1
출처
ACM ICPC Daejeon Regional 2015
로그인해야 코드를 작성할 수 있어요.