Legends

The country of Canadia consists of cities and roads. Each road can be traversed in both directions, and it is possible to get from any city to any other city using the roads.

Suzie studies the creation myths of the Canadiaan people. She is particularly interested in five myths, which correspond to the five subtasks of this problem. The myths are very similar. Each myth has the following form.

In the beginning, Canadia's road network had a particular structure. As time went on, the network was modified to meet the needs of Canadia's growing population. Each modification had one of the following forms:

• A road was built between two cities that did not yet have a road going directly between them.
• A new city was built. A city built this way is not initially connected to any existing city.
• A city $u$ grew too large and was split into two cities $v$ and $w$. The cities originally joined directly to $u$ by a road are partitioned into sets $A$ and $B$. A road is built from each city in $A$ to $v$, from each city in $B$ to $w$, and from $v$ to $w$.

For example, the city in the center of is split, and the network becomes .

The five myths differ only in the structure that they believe Canadia began with. The original structures according to each myth are as follows.

Subtask and myth	Picture	Original structure
1. The Myth of the Flask		4 cities $a, b, c, d$ and 5 roads $a$-$b$, $a$-$c$, $b$-$c$, $a$-$d$, $b$-$d$ (every pair of cities is joined except $c$ and $d$)
2. The Myth of the Moon		3 cities joined in a cycle by 3 roads (a triangle)
3. The Myth of the Sun		4 cities joined in a cycle by 4 roads
4. The Myth of the Eagle's Talon		1 city joined to each of 3 other cities (4 cities, 3 roads)
5. The Myth of the Fox		5 cities $a, b, c, d, e$ and 5 roads $a$-$b$, $b$-$c$, $c$-$a$, $a$-$d$, $b$-$e$ (a triangle with one extra city attached to each of two of its corners)

For each subtask, you are given the current layout of Canadia and must determine whether the myth might be correct, that is, whether some sequence of the modifications above (possibly empty) turns the myth's original structure into exactly the given layout, with city numbers disregarded.

The first line contains a single integer $S$ ($1 \le S \le 5$), the subtask to solve. The second line contains an integer $T$ ($1 \le T$), the number of test cases.

Each test case consists of a blank line, followed by a line with two integers $N$ and $M$ ($2 \le N$, $1 \le M$), the number of cities and roads. The cities are numbered from $1$ to $N$. Then $M$ lines follow, each containing two integers $a$ and $b$ ($1 \le a, b \le N$), meaning that cities $a$ and $b$ are connected by a road. No road connects a city to itself, and no two roads connect the same pair of cities. It is possible to get from any city to any other city using the roads.

In subtask 3, the sum of $N$ over all test cases is at most $10^5$, and the sum of $M$ over all test cases is at most $10^5$. In all other subtasks, the sum of $N$ over all test cases is at most $1000$, and the sum of $M$ over all test cases is at most $1000$.

For each test case, output a single line containing YES if the myth might be correct, or NO otherwise.