Mary, while walking home with her little lamb one day, saw an interesting graph theory problem. An undirected graph is called Funky if the vertices can be partitioned into two subsets, such that one subset is a clique and the other is an independent set. A subset is a clique if all the pairs of vertices in the subset are connected by a single edge. A subset is called an independent set as long as there is no pair of vertices in the subset which are connected by a single edge. Remember, that the partition may have one of the two subsets be empty. There may be edges between a vertex in the clique and a vertex in the independent set.
For those of you that don't know: An undirected graph is a set of "vertices" along with a set of "edges". Each edge is just a pair of vertices that it "connects". Each vertex can be represented by a positive number. Each edge can be represented by two numbers,
After looking at several examples Mary believes that she has discovered a pattern. It seems that in funky graphs, the vertex with the largest degreeis always in the clique's partition. Mary thinks that if she can figure out why this is the case (or why it's not always true) then it will really help her solve the problem. Help Mary figure out whether a given graph is funky.
There will be several test cases.
Each test case will begin with a line with two positive integers, V and E. V is the number of vertices. E is the number of edges. V will be at most 10000. The next E lines will contain two integers, the two vertices connected by an edge. Each of these numbers will be between 1 and V.
For each test case, output a line with the case number and "YES" if the graph is funky or "NO" if the graph is not funky.
4 4 1 2 1 3 2 3 1 4 4 4 1 2 2 3 3 4 1 4 3 3 1 2 1 3 2 3
1: YES 2: NO 3: YES