DRAWIT - Can you draw it or not?


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

Graph 1 Graph 2

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

For each test case, if the graph can be drawn so, print "YES" followed by a single space and the node from which you have to start drawing. If there are more than one node from where it's right to start drawing, print the node with the least value.

If the graph can't be drawn so, just print "NO".

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:
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.


hide comments
citizendot: 2021-08-16 15:26:28

Hint: <snip>

Last edit: 2023-05-21 13:41:32
sanchit_aga: 2019-01-11 09:21:41

Good problem, enjoyed solving it.

holmesherlock: 2018-01-26 18:20:54

Euler :-)

nadstratosfer: 2017-12-18 16:23:01

Input contains blanklines, take care of these when solving in Python or Java else NZEC.

Sankaranarayanan G: 2017-07-24 10:42:15

@soumikrashit

I have provided links to those images in the "Note" section. Try checking those.

soumikrakshit: 2017-07-02 22:33:03

Images of the graphs are not coming. Please help!!!!

sonudoo: 2017-06-19 20:27:54

Test cases are strong.

Vladimir: 2017-01-05 21:05:32

Is input format ok? My python solution gives runtime error, and as I see another attempt of python solution had same error as well...

Karsten Ari Agathon: 2016-12-31 14:58:32

I couldn't find my mistakes on submission #18489608. Please help me. Thanks.


Added by:mombassa
Date:2016-12-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU