URI Online Judge | 1610

Dudu Service Maker

By Rafael Regis, Universidade de São Paulo - São Carlos BR Brazil

Timelimit: 1

Dudu needs a document to finalize a task in his work. After searching, he found out that this document needed other documents, which also needed other documents and so on.

Dudu made a final list with the documents he will need. With that in hands, he suspects that the list contains loops. For instance, if a document A depends on the document B that also depends on A, it would make the task impossible to finish. In this case the loop contains only two documents, but there might be cases with three or more!

Given the list of the dependencies, help him compute if he can obtain all the documents, it is, to compute if there isn't a loop in the given dependencies.

Input

The first line contains an integer T (T = 100) indicating the number of test cases.

On the first line in each test case there will be the integers N (2 ≤ N ≤ 100* or 2 ≤ N ≤ 104**) and M (1 ≤ M ≤ 300* or 1 ≤ M ≤ 3*104​**), indicating the number of documents and the dependencies. In each of the following M lines, there will be two integers A (1 ≤ A) and B (BN and A != B) , indicating that the document A depends on the document B. There might be repeated dependencies!

*For around 90% of the cases;

**For the other cases.

Output

For each case, print SIM (Portuguese word for YES) if there is at least one loop, and NAO otherwise (Portuguese word for NO).

Sample Input Sample Output

3

2 1

1 2

2 2

1 2

2 1

4 4

2 3

3 4

4 2

1 3

NAO

SIM

SIM