Man in the Middle

Interview

Time limit3sMemory limit256 MB

Summary
Decide whether removing some single person disconnects the connected friendship network.
Level

Medium4 of 10

Topics
DFS, Graph
Solved
No attempts yet

Problem

In a connected social network, a Man in the Middle is a person whose departure disconnects the network. Report whether any such person exists.

Input

The first line contains TT test cases (T≤15T \le 15). Each test case gives NN, MM, and MM friendship pairs.

Output

Print YES if the network has a Man in the Middle, otherwise print NO.

Examples1

  1. Example 1

    Input
    2
3 2
1 2
1 3
4 4
1 2
1 3
2 4
3 4
    Expected output
    YES
NO