# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Circuit Breaker

By d1xlord · Limits 1s, 512 MB

In your free time, you like to design various electrical circuits to give a hard time to your local circuit makers by ordering them to build it for you.

Recently, a skilled circuit maker has appeared in town and helping all the others by representing your given circuits as a planar graph. A planar graph is such a graph that can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. It is crucial for a circuit to be a planar graph. You should also note that, even if you draw a graph and think it as non-planar, it maybe possible to represent it as a planar graph. On the image below, by looking at the first image, it may seem like it's a non-planar graph. But it can represented in the following two ways as a planar graph. So previously the circuits you designed thinking as a non-planar graph was somehow represented as a planar graph by this newcomer.

Now for tackling this skilled maker, you have to give him a non-planar graph, so that he cannot build a circuit using it. You have already written a computer program that generates a random connected simple graph. Now your work is to determine if the generated graph is non-planar or not.

Checking planarity is hard. After some digging, you came upon these following formula which will ensure that if the conditions are true, the graph will be non-planar. There might be some graphs which are non-planar and doesn't meet these conditions but you don't want to be bothered by them. (The conditions are necessary but not sufficient)

For a connected planar graph having v vertices and e edges, where v ≥ 3, the following holds:

• If there are no cycles of length 3, then e ≤ 2v − 4.
• Else, e ≤ 3v − 6.

Using this formula, you job is to check for each given graph, if it is non-planar or not.

## Input

Input starts with an integer T (≤ 110), denoting the number of test cases.

Each test case starts with a line containing two integers, V and E (0 ≤ V ≤ 1000, 0 ≤ E ≤ 4000). Each of the next E lines contains two integers, x and y, an edge between vertices x and y (0 ≤ x, y < V).

## Output

For each test case, print the case number and “Yes” or “No”, without the quotes, depending on the graph being non-planar or not.

## Sample

InputOutput
2
3 3
0 1
0 2
1 2
5 10
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4
Case 1: No
Case 2: Yes

### Statistics

67% Solution Ratio

zscoderEarliest, Dec '16

NorendroFastest, 0.0s

NorendroLightest, 131 kB

oneoff.ciu7BMmRThShortest, 594B

Login to submit

### Related Contests

 SUST Intra University Programming Contest 2017 (Junior) Selection 2Ended Jul '17 Replay of Cybernauts'16 National Programming ContestEnded Dec '16 Cybernauts'16 National Programming ContestEnded Oct '16
Toph uses cookies. By continuing you agree to our Cookie Policy.