음수 사이클

자기 루프나 중복 간선이 없는 단순 무향 그래프 G를 생각하자. G의 두 정점 x와 y에 대해, G에서 x에서 y로 가는 경로는 G의 서로 다른 정점의 나열 <v1, v2, … , v**ℓ>로서 v1 = x, v**ℓ = y이고 모든 i ∈ {1, … , ℓ − 1}에 대해 vi가 v**i+1과 인접한 것이다. ℓ ≥ 3이고 v**ℓ가 v1과 인접하면 그 경로를 사이클이라고 한다. 각 간선에 +1 또는 −1의 가중치가 부여된 그래프에서, 사이클에 속한 간선들의 가중치 곱은 +1 또는 −1이 된다. 가중치 곱이 −1이면 그 사이클을 음수 사이클이라 하고, 그렇지 않으면 양수 사이클이라 한다. 아래 그림의 그래프를 예로 보자. 왼쪽 그래프에는 음수 사이클 <v1, v2, v3>과 <v1, v3, v4>가 있고 양수 사이클 <v1, v2, v3, v4>도 있다. 오른쪽 그래프에는 음수 사이클이 없고 양수 사이클 <v1, v2, v3, v4>, <v1, v4, v5>, <v1, v2, v3, v4, v5>가 있다.

입력으로 주어진 그래프에 음수 사이클이 존재하는지 판별하고, 존재하면 임의의 음수 사이클 하나를 출력하는 프로그램을 작성하시오.

프로그램은 표준 입력에서 데이터를 읽는다. 첫째 줄에는 단순 무향 그래프의 정점 수와 간선 수를 나타내는 두 양의 정수 n과 m이 주어지며, n ≤ 20,000, m ≤ 200,000이라고 가정한다. 정점에는 1부터 n까지 번호가 붙는다. 이어지는 m개의 줄 각각에는 간선 (x, y)와 그 가중치 w ∈ {+1, −1}을 나타내는 세 정수 x, y, w가 주어진다. 한 줄에 주어지는 정수들은 항상 공백 하나로 구분된다.

프로그램은 표준 출력에 결과를 쓴다. 첫째 줄에는 주어진 그래프에 음수 사이클이 있는지를 나타내는 정수를 출력한다. 있으면 1, 없으면 -1을 출력한다. 첫째 줄이 1인 경우에만, 그 뒤에 입력 그래프의 임의의 음수 사이클에 대한 설명을 출력한다. 사이클은 길이를 나타내는 정수 ℓ을 담은 한 줄과, 그 뒤에 임의의 정점에서 시작하여 사이클을 따라갈 때 만나는 정점들을 하나씩 담은 ℓ개의 줄로 표현된다. 사이클의 정점들은 서로 달라야 한다.