Shortest paths - interesting graph problems
Cycles in the graph
Given an undirected graph without loops and multiple edges. Determine whether there are cycles in the graph, and, if so, find the vertex with the smallest number belonging to at least one of the cycles.
The first line contains two integers n and k (1 ≤ n ≤
105, 0 ≤ k ≤
105) - the number of vertices and edges in the graph. Followed by k lines, each contains a pair of distinct integers a, b (1 ≤ a, b ≤ n) which means that there is an edge in the graph between the vertices a and b. Each pair of a, b does not occur more than once.
If the graph contains no cycles, print a single word No. Otherwise, print in the first line Yes and in the next line print the smallest number of vertex belonging to at least one cycle.
6 6 1 2 2 3 3 4 4 5 5 2 4 6