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.

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

提交代码