DFS + Cycles + Cactus

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 (1n105, 0k105) - the number of vertices and edges in the graph. Followed by k lines, each contains a pair of distinct integers a, b (1a, bn) 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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
6 6
1 2
2 3
3 4
4 5
5 2
4 6
Output example #1
Author A. Milanin
Source ACM, Ukraine, First Stage, 09.04.2011