Description

Given a directed graph $D$ with $n$ vertices and $m$ edges, construct a graph $E$ as follows: for each edge $(u,v)$ in $D$, create a vertex $uv$ in $E$; then for any two edges $(u,v)$ and $(v,w)$ in $D$, add a directed edge from $uv$ to $vw$ in $E$. No other vertices or edges exist in $E$.

Given $E$, your task is to determine whether there exists a corresponding $D$.

Note that $D$ may have parallel edges and self-loops.

Input Format

The first line contains the number of test cases $T$ ($T\leq 10$).

For each test case:

The first line contains an integer $m$ ($0\le m\le 300$), the number of edges in $D$ (i.e., the number of vertices in $E$).

The second line contains an integer $k$, the number of edges in $E$.

Each of the following $k$ lines contains two integers $x, y$, indicating that there is a directed edge $(x,y)$ in $E$. The vertices in $E$ are numbered from $0$ to $m-1$.

Output Format

For each test case, output one line. If it exists, output Yes; otherwise, output No.

4
2
1
0 1
5
0
4
3
0 1
2 1
2 3
3
9
0 1
0 2
1 2
1 0
2 0
2 1
0 0
1 1
2 2

Yes
Yes
No
Yes

Hint

Translated by ChatGPT 5