Triple Route Test

Jeremy, Richard and James love testing cars. They select a country with several cities and two‐way roads connecting them. To perform a test, they must choose two distinct cities \(S\) and \(F\) such that there exist three routes between them. These routes must satisfy that:

• Each city other than \(S\) and \(F\) appears in at most one route.
• No road is used more than once across the three routes.

This condition is equivalent (by Menger's Theorem) to the existence of three internally vertex‐disjoint paths between \(S\) and \(F\) in the given undirected graph.

You are given several countries. For each country, determine if it is possible to choose two cities \(S\) and \(F\) satisfying the above conditions.

Note: In our formulation, the graph’s vertices (except \(S\) and \(F\)) have a capacity of 1, so that they can be used by at most one route. The roads (edges) are two–way and can be used only once.

inputFormat

The first line contains an integer \(T\) denoting the number of test cases (countries). For each test case, the first line contains two integers \(n\) and \(m\) where \(n\) is the number of cities and \(m\) is the number of two–way roads. The following \(m\) lines each contain two integers \(u\) and \(v\) (1–indexed) indicating there is a road between city \(u\) and city \(v\).

outputFormat

For each test case, print a single line containing YES if it is possible to choose two cities with three vertex–disjoint routes between them, and NO otherwise.

sample

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

NO
YES
YES
NO