H. Homework
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Riko was given an interesting problem as part of her graph theory homework.

You are given a graph with $$$n$$$ vertices and $$$m$$$ edges. Some of the edges are directed, while the rest are undirected. You must determine if it's possible to assign directions to all the undirected edges in such a way that the edges of the resulting directed graph can be partitioned into directed edge-disjoint cycles.

Help Riko solve her homework so she can go read her books!

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 300$$$, $$$1 \le m \le \frac{n(n - 1)}{2}$$$) — the number of vertices and the number of edges in the graph respectively.

Each of the following $$$m$$$ lines contains three integers $$$u, v, d$$$ describing an edge. ($$$1 \le u \le n$$$, $$$1 \le v \le n$$$, $$$d \in \{0, 1\}$$$, $$$u \neq v$$$) If $$$d = 0$$$ then this is an undirected edge between vertices $$$u$$$ and $$$v$$$. If $$$d = 1$$$ then this is a directed edge from vertex $$$u$$$ to vertex $$$v$$$.

It is guaranteed that any two vertices have at most one edge connecting them.

Output

Print a single line containing YES if it is possible to direct the edges as desired, and NO otherwise.

Examples
Input
6 12
1 2 1
1 3 1
1 5 0
1 6 0
2 3 0
2 4 0
2 6 1
3 4 1
3 5 0
4 5 1
6 4 1
6 5 0
Output
YES
Input
6 12
1 2 1
1 3 1
1 5 0
6 1 1
2 3 0
2 4 0
2 6 1
3 4 1
3 5 0
4 5 1
6 4 1
6 5 1
Output
NO