Problem A
Harmony and conflict

Consider an unweighted, undirected, simple, loopless graph $G$ with vertex set $\{ 0,\ldots ,n-1\} $. Each edge in $G$ is called either a conflict edge or harmony edge. A harmonious 2-colouring is an assignment of each vertex to one of 2 colours such that

1. the end points of each conflict edge have different colours, and

2. the end points of each harmony edge have the same colour.

Your task is to determine if $G$ can be harmoniously 2-coloured.

In the four example graphs below, which correspond to the sample inputs, conflict edges are drawn as full lines; harmony edges are drawn as dashed lines. The first two graphs can be harmoniously 2-coloured; examples of such colourings are shown. The last two graphs cannot be harmoniously 2-coloured.

     

Input

On the first line of input, the integers $n$ and $m$, giving the number of vertices and the number of edges in the graph. You can assume $1\leq n\leq 100\, 000$ and $0\leq m \leq 100\, 000$. Each of the following $m$ lines describe a single edge; the format are three space-separated integers $u\ v\ c$ with $0\leq u< v<n$ and $c\in \{ 0,1\} $. The endpoints of the edge are $u$ and $v$; the edge is a conflict edge if $c=1$, otherwise it is a harmony edge.

Ouput

“1” if the graph can be harmoniously 2-coloured, else “0”.

Test groups

There are a number of test groups of increasing generality.

13 15
0 1 1
0 2 1
0 5 1
0 6 1
1 3 1
3 5 1
4 5 1
4 6 1
6 7 1
7 8 1
8 10 1
9 10 1
10 12 1
11 12 1
9 11 1

1

13 18
0 1 1
0 2 1
0 5 1
0 6 1
1 3 1
3 5 1
4 5 1
4 6 1
6 7 1
7 8 1
8 10 1
9 10 1
10 12 1
11 12 1
9 11 1
6 9 0
8 9 0
3 4 0

1

4 5
0 1 1
1 2 1
2 3 1
0 3 0
0 2 0

0

3 3
0 1 1
1 2 1
0 2 1

0