Given an directed graph of n vertices and m edges. Some edges already have direction, but some are not. Direct undirected edges so that the resulting graph is acyclic.
### Input
- The first line contains two integers n,m.
- The next m lines, each line contains three integers t,u,v, there is an edge connect u and v. If t=0, this edge is not directed. If t=1, this edge is directed from u to v. It is guaranteed that the graph contains no self-loop and multiple edge.
### Output
- Print NO if there is no way to direct edges. Otherwise print YES, the next m lines describing edges of the resulting graph (in any order). You can not change the direction of already directed edges.
### Constraints
- 1≤n,m≤105.
- 1≤u,v≤n.
### Example
Input:
45112043131023124
Output:
YES1234313224
