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
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 1Output: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
hide comments
citizendot:
20210816 15:26:28
Hint: Euler Path 

sanchit_aga:
20190111 09:21:41
Good problem, enjoyed solving it. 

holmesherlock:
20180126 18:20:54
Euler :) 

nadstratosfer:
20171218 16:23:01
Input contains blanklines, take care of these when solving in Python or Java else NZEC. 

Sankaranarayanan G:
20170724 10:42:15
@soumikrashit


soumikrakshit:
20170702 22:33:03
Images of the graphs are not coming. Please help!!!! 

sonudoo:
20170619 20:27:54
Test cases are strong. 

Vladimir:
20170105 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:
20161231 14:58:32
I couldn't find my mistakes on submission #18489608. Please help me. Thanks. 
Added by:  mombassa 
Date:  20161230 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 