Two papers II

3.7

12 votes
Algorithms, Biconnected Components, Biconnected component, Depth First Search, Graphs
Problem

M found two papers and a pencil in his room (as you know it's so valuable for a prisoner). a weighted (weights are either 0 or 1) graph is drawn on the first paper.

M is forced to draw a spanning tree of the graph (which is drawn on the first paper) on the second paper which includes odd number of 1 weighted edges.

Can M draw a spanning tree with the conditions described above?

Input

First line contains two integers n,m, number of first paper graph's vertices and number of first paper graph's edges.

Each of the following m lines contains vi,ui and wi separated space describing graph's ith edge's vertices(vi,ui) and its weight (wi).

Output

In the only line of output print YES if M can draw a spanning tree of the first paper's graph with odd number of 1 weighted edges and otherwise print NO.

Constraints

1n,m3×105

1vi,uin0wi1

It is guaranteed that there is no multiple edges or self loops in the graph.

Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

There is only one spanning tree which has 3 number of 1 weighted edges.

Editor Image

?