D. Do The g, Man
time limit per test
8 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

At the Institute of Maximum Efficiency, otherwise known as IME, we must honor those who come before us as they have built the path through which we walk. The person of highest honors, of course, is the general of the institution, who is the one responsible for making the toughest decisions in order to run the institution with maximum efficiency. As he is oh so important, there have to be certain references to him in every minute detail in this grandiose institute!

Suddenly, on one fine Wednesday afternoon, at around $$$14:00$$$, the general decided to run a contest: let's figure out who can make the most beautiful graph of all time! Some random criteria were established that fit his own needs; however, there were too many graphs submitted for the contest as everyone at the institute voluntarily participated in this event. As such, he decides, for some reason, that you're the most fit person to help him filter out the graphs. One of the criteria that you think will filter out the largest amount of graphs is doing the g inside of a graph. That being, if a graph has a g as a subgraph, then it will be automatically passed on to the next phase of this contest. Of course, only a select amount of students at the institute will have the intellectual power to create such a graph.

A graph has a g as a subgraph if you're able to find a simple cycle of length 4 and then have a tail of size $$$2$$$, because the general saw that if you rearrange these edges in a certain way, it looks like a g, a g for general, of course! A tail in this case is a path of length $$$2$$$ that starts in any vertex of the cycle and doesn't intersect it.

Here you can see two graphs; the one on the left has done the g, while the one on the right hasn't.
Input

The first line contains an integer $$$t$$$, $$$(1 \leq t \leq 100)$$$ — the number of graphs that the general will give to you.

The first line of each test case consists of two integers, $$$n$$$, $$$m$$$ $$$(1 \leq n \leq 3 \times 10^3)$$$ $$$(0 \leq m \leq \min(10^6, \frac{n \times (n - 1)}{2}))$$$ — the amount of nodes and edges in the given graph.

The next $$$m$$$ lines of each test case consist of two integers, $$$a$$$, $$$b$$$ $$$(1 \leq a, b \leq n)$$$, $$$(a \neq b)$$$ — indicating that nodes $$$a$$$ and $$$b$$$ are connected. Note that the graphs do not contain multi-edges nor loops.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3000$$$.

Output

For each test case, print out YES if you're able to do the g and NO otherwise.

You may output each letter in any case (lowercase or uppercase). For example, the strings yEs, yes, Yes, and YES will be accepted as a positive answer.

Example
Input
2
8 10
1 2
1 3
2 4
2 5
4 5
5 6
2 3
3 6
3 7
7 8
8 12
1 2
1 3
1 4
2 3
2 4
3 4
5 6
5 7
5 8
6 7
6 8
7 8
Output
YES
NO