Minimum Vertex Removal for an Acyclic Graph

Given an undirected connected graph \(G=(V,E)\) with \(N\) vertices and \(M\) edges, your task is to determine a minimum set \(S\) of vertices whose removal makes the remaining graph acyclic (i.e. a forest). In this problem, if the graph contains any cycle, it can be broken by removing a single vertex from that cycle.

If the graph is already acyclic, simply output \(0\). Otherwise, output the size of \(S\) (which will be \(1\)) and any vertex belonging to a cycle.

Note: It is guaranteed that if the graph is not acyclic, removing one vertex from any cycle will render the graph acyclic.

inputFormat

The first line contains two integers (N) and (M) (where (1 \le N \le 10^5) and (0 \le M \le 10^5)). Each of the next (M) lines contains two integers representing an undirected edge between two vertices (vertices are numbered from 1 to (N)).

outputFormat

If the graph is already acyclic, output a single line containing 0. Otherwise, output two lines: the first line contains 1 (the size of the vertex set (S)); the second line contains one vertex (any vertex that is part of a cycle).## sample

5 5
1 2
2 3
3 4
4 5
5 1

1
5