XiaoMing's Problem

Time Limit: 5000 ms

Memory Limit: 65535 ms

Description

Our little young Xiaoming is a really lovely boy.And he always has a lot of funny ideas. In recent times, he decides to travel to see beautiful scenaries, such as Nanjing University of Science and Technology. However, he also hears that there are really many beautiful girls in Sichuan Province. Things do not come easy. What troubles him so much is that since there are some places which he can only go from or go to(the transportation is not that convenient), in some circumstances he cannot go back home in any ways. Here comes your problem. Try to help XiaoMing to decide if it is possible.

Input

The first line contains the test cases. The second line tells you the number of the places N and the number M of the roads between them. Then M lines follow. Each line has three numbers which mean the the two places .For example 1 2 0 tells that XiaoMing can go from 1 to 2 or from 2 to 1.If the third number is 1,it means that he can only go from 1to 2 in the only direction.If the number is 0,it means that he can go from 1 to 2 and also can go from 2 to 1.On the other hand, if the two numbers come twice the same as some others that is listed above, it means he should go twice. Totally he should go every way which is listed, and he should return to his starting point in the end.(His starting point is unknown at the beginning.)

Output

If he can go back home and go every way, print “ Yes”. Else print “No”.

Sample Input

2
5 6
1 3 0
3 1 0
1 2 1
2 5 1
5 4 0
4 3 1
5 8
2 1 0
1 3 0
4 1 1
1 5 0
5 4 1
3 4 0
4 2 1
2 2 0

Sample Output

No
Yes

Hint

Source

ZhangJunHua

提交代码