当前没有测试数据。

Given a graph, you have to find if the graph can be drawn without taking the hands away. Assume that you are going to draw the given graph on a paper and you have to find whether you can draw it at a single stroke, i.e, without taking the hands away. And also, you are allowed to draw the graph only once. That is, you can't draw a single edge more than once. The given graph will have N nodes, numbered from 1 to N.

Consider the following graphs. For input clarity of the graphs, refer to the sample input

Input

The first line has the number of test cases, T.

Then for each test case, the first line has the integer N, the number of nodes.

The second line has the integer K.

Then K lines follow that, each line having three integers S, D, M denoting that there are M edges between the two nodes S and D.

Constraints

1 <= T <= 50

1 <= N <= 100

1 <= K <= (N * ( N – 1) ) / 2

1 <= S, D <= N

1 <= M <= 100

Output

Example

Input:
2
4
6
1 2 2
1 3 1
1 4 2
2 3 2
2 4 1
3 4 2
5
10
1 2 1
1 3 1
1 4 1
1 5 1
2 3 1 
2 4 1
2 5 1
3 4 1
3 5 1
4 5 1
Output:</p>
NO
YES 1

Note:
1) If there are more than one edge between two nodes, assume that those edges are of different forms. See the above picture for more clarity.
2) If there are M edges from S to D, then there are also M edges from D to S.
3) If you can't view the images, go to 
IMG 1: https://www.dropbox.com/s/5smf3qpepzn3juw/pic1.png?dl=0 
IMG 2 : https://www.dropbox.com/s/ys2gmdmatq83l4s/Shp6.jpg?dl=0