20043번 - Negative Cycle 스페셜 저지다국어채점 준비 중

Let G be a simple undirected graph having no self-loops or multiple edges. For two vertices x and y of G, a path from x to y in G is a sequence <v₁, v₂, … , v_ℓ> of distinct vertices of G such that v₁ = x, v_ℓ = y, and v_i is adjacent to v_i+1 for all i ∈ {1, … , ℓ − 1}. If ℓ ≥ 3 and v_ℓ is adjacent to v₁, the path is called a cycle. In a graph in which a weight of +1 or −1 is assigned to each edge, the weight product of the edges in a cycle will be +1 or −1. If the weight product is −1, the cycle is called a negative cycle; it is called a positive cycle otherwise. Refer to the graphs shown below for illustrative examples. The left graph contains negative cycles <v₁, v₂, v₃> and <v₁, v₃, v₄> and also positive cycle <v₁, v₂, v₃, v₄>, whereas the right graph contains no negative cycle, but positive cycles <v₁, v₂, v₃, v₄>, <v₁, v₄, v₅>, and <v₁, v₂, v₃, v₄, v₅>.

Write a computer program that determines the existence of a negative cycle in the graph given as an input and report an arbitrary negative cycle, if any.

Your program is to read from standard input. The first line contains two positive integers n and m, respectively indicating the numbers of vertices and edges of a simple undirected graph, in which we assume n ≤ 20,000 and m ≤ 200,000. The vertices are indexed from 1 to n. In the following m lines, each line contains three integers x, y, and w ∈ {+1, −1}, which represent an edge (x, y) of weight w. The integers given in a single line are always separated by a single space.

Your program is to write to standard output. The first line must contain an integer indicating whether the given graph has a negative cycle. If yes, the integer must be 1; otherwise -1. When and only when the first line is 1, it must be followed by the description of an arbitrary negative cycle of the input graph. A cycle is described by a single line containing an integer ℓ, representing its length, followed by ℓ lines containing, one by one, the vertices encountered when we traverse the cycle starting from an arbitrary vertex. Note that the vertices of the cycle must be distinct.