33378번 - Institute 다국어

문제

Tikhon passed the entrance exams, and now studies at a research institute. However, he is afraid to walk around its campus. He is worried that he may forget his pass somewhere and permanently lose it, and then he will not be able to attend classes.

The campus of Tikhon's institute is a directed graph. Some of the edges of this graph can only be traversed with a pass.

To lose the pass permanently, Tikhon would need to start at his dormitory, which is located at the first vertex, then walk along zero or more edges of the campus, then leave his pass in some vertex, continue walking around the campus, and then not be able to return to the vertex where he has left the pass.

Tikhon would like to know if he is worried for no reason: please help him find out if it is possible to permanently lose the pass in the campus.

입력

The first line contains two integers $n$ and $m$ (1ドル \le n, m \le 3 \cdot 10^5$): the number of vertices and edges in the graph, respectively.

Each of the following $m$ lines contains three integers $u_i,ドル $v_i,ドル $t_i$ (1ドル \le u_i, v_i \le n$; 1ドル \le t_i \le 2$) describing the directed edges of the graph. Edge $i$ allows passage from $u_i$ to $v_i$. If a pass is required to go through edge $i,ドル then $t_i = 1,ドル otherwise $t_i = 2$.

The given graph may contain loops and multiple edges between the same vertices.

출력

Print a line with a single word (case-insensitive): "Yes" if Tikhon can permanently lose his pass, or "No" otherwise.

제한

노트

In the first example, Tikhon can first traverse the edge 1ドル \rightarrow 2$ with a pass, then, leaving a pass at vertex 2ドル,ドル traverse the edge 2ドル \rightarrow 3$. After that, he will not be able to return to vertex 2ドル$.