P4575 [CQOI2013] Inverse Transformation of a Graph

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.

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$.

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

Translated by ChatGPT 5