Cycle Detection in an Undirected Graph

You are given an undirected graph with \(N\) nodes and \(M\) edges. Your task is to determine whether there is a cycle in the graph. If a cycle exists, you must output "YES" on the first line and on the second line output the sequence of nodes that forms the cycle, with the first node repeated at the end to clearly indicate the cycle. Otherwise, output "NO".

Formally, given a graph \(G = (V, E)\) where \(|V| = N\) and \(|E| = M\), a cycle is a sequence of nodes \(v_1, v_2, \dots, v_k, v_1\) such that each consecutive pair \((v_i, v_{i+1})\) is an edge in \(E\) (with \(v_{k+1} = v_1\)) and \(k \ge 3\).

It is guaranteed that the node labels are from 1 to \(N\). Note that the graph may be disconnected; in such a case, you should check every connected component.

inputFormat

The first line of input contains two integers \(N\) and \(M\) (the number of nodes and edges, respectively). Each of the following \(M\) lines contains two integers \(u\) and \(v\), representing an undirected edge between nodes \(u\) and \(v\).

outputFormat

If a cycle exists, print "YES" on the first line and on the second line print the nodes in the order they appear in the cycle (with the first node repeated at the end). If no cycle exists, print "NO".

3 2
1 2
2 3

NO