Background

Problem Description

We know that in plane geometry, triangles are stable shapes.

Xiao L drew a graph on paper. He told you the number of points in the graph and which pairs of points are connected by edges. He wants to know whether this graph is stable.

We say a graph is stable if and only if: after choosing any one edge and fixing it so that it cannot move, then all the other edges and points cannot move either. Note that movement is only within the plane, i.e., reflections are not allowed. In particular, a single point is stable.

For example, a line segment or a triangle is stable, but a quadrilateral is not stable.

Note that you may assume stability has nothing to do with the lengths of edges. So as long as there exists a set of edge lengths that makes the graph stable, it is stable. If no such set of edge lengths can satisfy the condition, then it is unstable.

Input Format

The input consists of multiple lines.

The first line contains one positive integer $T$, the number of test cases.

Then for each test case, the input contains $m + 1$ lines:

• Line $1$ contains two integers, the number of vertices $n$ and the number of edges $m$.
• Lines $2$ to $m + 1$ each contain two integers, the indices of the two vertices connected by an edge.

Output Format

Output $T$ lines.

For each test case, output one line containing one string. Output $\tt Yes$ if the graph is stable, otherwise output $\tt No$. In particular, if the given information cannot form a graph, output $\tt No$.

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

Yes
No

1
4 5
1 2
2 3
3 4
4 1
1 3

Yes

Hint

Constraints

• For $50\%$ of the testdata, $n \le 50$, $m \le 2 \times 10^3$.
• For $100\%$ of the testdata, $1 \le T \le 10$, $1 \le n \le 2 \times 10^2$, $0 \le m \le 2 \times 10^4$. Self-loops are guaranteed not to exist, but multiple edges may appear.

Translated by ChatGPT 5