Check if the Graph is Efficient
Given an undirected graph with
v vertices and e edges, you are asked to check if it’s efficient. A graph is considered efficient if it is possible to travel from any node to any other node by traversing at most 2 edges.Input
The first line of the input contains two integers
v (1 ≤ v ≤ 100) 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 efficient, and No otherwise.Examples
Input | Output |
4 3
1 2
2 3
3 1 | No |
4 4
1 2
2 3
3 1
1 4 | Yes |
Explanation
- Vertex 4 is not connected to the others ⇒ it’s not possible to get from vertex 4 to any other by traversing at most 2 edges.
- It’s possible to get to any vertex from any other vertex by traversing at most 2 edges.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB