问题 D: Koraidon, Miraidon and DFS Shortest Path

One day, Koraidon gave Miraidon a directed graph with $n$ vertices and $m$ edges. The weights of all edges are $1$. Koraidon asked Miraidon to calculate the shortest path from vertex $1$ to each vertex. It is guaranteed that vertex $1$ can reach all other vertices through the edges.
However, Miraidon just forgot the BFS algorithm. He tried to use the DFS algorithm as a replacement. The algorithm looks like:

In line $4$, Miraidon tried to use a random shuffle function to get a correct answer. The shuffles in different recursive calls of DFS are mutually independent.
Koraidon judged the answer given by Miraidon very strictly. He would consider the algorithm correct if and only if the algorithm gives correct answers on all possible random shuffle results.

Each test contains multiple test cases.
The first line contains an integer $T$ (1≤T≤5×1051\leq T\leq 5\times10^{5}1≤T≤5×105) – the number of test cases.
For each test case:
The first line contains two integers $n,m$ (1≤n,m≤5×1051\leq n,m\leq 5\times 10^51≤n,m≤5×105).
Each of the next $m$ lines contains two integers $u$ and $v$ (1≤u,v≤n1\le u,v\le n1≤u,v≤n), denoting a directed edge from $u$ to $v$. The graph is not guaranteed to be a simple directed graph. But it is guaranteed that vertex $1$ can reach all other vertices through the edges.
It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed 5×1055\times10^{5}5×105.

For each test case, print “Yes” if the algorithm is correct on this graph, and “No” otherwise.
You can output the answer in any case (upper or lower). For example, the strings “yEs”, “yes”, “Yes”, and “YES” will be recognized as positive responses.

2
3 3
1 2
2 3
3 1
3 3
1 2
1 3
2 3

Yes
No