Poltu is back again. As he is a fresher in KUET, he is learning new things everyday. He wants to register courses for his new semester. But as he has found out, course registration can be a long and a tiresome work. And, Poltu does not know how to do course registration. So he has asked his best friend Boltu for help.
Boltu said that, he has to complete a set of tasks for course registration. But as always, there's a catch. Boltu said Poltu that he cannot complete the tasks in any order. Some tasks depends on others and they have to be completed first to complete the dependent tasks. More specifically, a certain task can (or can not) depend on completion of some other task. So you are given a the number of tasks N and the list giving the description which task depends on which task.
Now Goltu said Poltu that Boltu has been having some trouble remembering things and he keeps saying wrong facts to everyone. So, if Boltu said that the task u is dependent on v then it is probable that the relation was actually inverse, that is, the task v is dependent on u but as Boltu is forgetful, he told the wrong information to Poltu.
Poltu thinks that the dependency relation between all the tasks should not have any cycle. But as Boltu is forgetful, the dependency relation given by Boltu may have a cycle. Now Poltu wants to fix this dependency relation. But as he is lazy and tired, he has come to you.
So you are going to help him. Can you change the dependency list so that it does not contains any cycle by reversing at most one dependency relation? Reversing a dependency relation means that if an relation was u dependent on v then you can consider the relation as v dependent on u but you can do this for at most one dependency relation.
The first line contains T (1 ≤ T ≤ 10). The details for each test case is as follows:
The first line for each test case contains N (1 ≤ N ≤ 1000) and M (1 ≤ M ≤ 1000). The numbers represent the number of tasks and number of dependency relations respectively.
Next M line describes dependency relations. Each line contains two integers u (1 ≤ ui ≤ N) and v (1 ≤ vi ≤ N). This means that the task u is dependent on task v.
Output one line for each test case. Each case must follow this format:
If the dependency list can be changed so that it does not contain any cycle by reversing at most one dependency relation then print "Yes" (without quotes), otherwise print "No" (without quotes).
| Input | Output |
|---|---|
3 5 4 1 3 2 3 3 4 4 5 6 8 1 2 2 3 3 4 4 1 2 5 5 1 4 6 6 3 3 3 1 2 2 3 3 1 | Yes No Yes |