#P7986. Pty loves graph

Pty loves graph

Pty loves graph

Given a undirected graph and a Hamiltonian cycle of it, output whether it is a planar graph.

For convenience, the indices of vertex are advancely relabeled so that the given Hamiltonian cycle is 1,2,…,N,11,2,\ldots,N,1. The edges on this cycle are not given in the input.

Notice that there might be self loops and multiedges in the graph.

There are TT test cases in total.

A planar graph admits some drawing with no crossings except at common endpoints. The vertices need not remain on a circle, and the extra edges need not be straight segments. The Hamiltonian cycle edges are present implicitly, in addition to the MM listed edges.

输入格式

The first line contains one integer T–T–the number of test cases.

For each test case:

The first line, two positive integer N,MN,M - the number of vertices and edge besides the Hamiltonian cycle. Following mm lines, two positive integer x,yx,y, representing an edge (x,y)(x,y).

1≤T≤261\le T\le 26 1≤N,M≤5×1051\le N,M\le5\times10^5, ∑N,∑M≤3×106\sum N,\sum M\le3\times10^6 over all cases.

1≤x,y≤N1\le x,y\le N

输出格式

For each test case, output ”Yes” or ”No” in one line.

样例输入1

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

样例输出1

No
Yes