Check if the Graph is a Crown
Given an undirected graph with
v vertices and e edges, you are asked to check if it’s a crown graph. A crown consists of a base and may have any number of spikes. The Crown's base consists of a single edge connecting two nodes, and it is a common edge for all the spikes, every spike has only one node connected to both sides of the base.
Input
The first line of the input contains two integers
v (1 ≤ v ≤ 1000) and e (1 ≤ e ≤ 10 000).The following
e lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) representing an edge between v1 and v2.Output
The program should print
Yes if the graph is a crown graph, and No otherwise.Examples
Input | Output |
4 4
1 2
2 3
3 1
1 4 | No |
7 11
3 4
2 3
2 4
1 3
1 4
7 3
7 4
6 3
6 4
5 3
5 4 | Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB