Check if a Graph Is a Star Graph
Given an undirected graph with
v vertices and e edges, you are asked to determine if it’s a star graph. A star graph is a graph that has a central vertex that is connected to all the other vertices, while all the other vertices are only connected to the central one and no other vertex.
Input
The first line of the input contains two integers
v (1 ≤ v ≤ 100 000) and e (1 ≤ e ≤ 100 000).The following
e lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) which means that the vertex v1 is connected to the vertex v2 and vice versa.Output
The program should print
Yes if the graph is a star graph and No otherwise.Examples
Input | Output |
7 6
1 5
2 5
3 5
7 5
6 5
4 5 | Yes |
7 6
1 5
2 5
3 5
7 5
6 1
4 5 | No |
1 0 | Yes |
2 1
1 2 | Yes |
2 0 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB