Graph Partitioning Challenge

You are given a connected undirected graph with $N$ nodes and $M$ edges. Your task is to determine whether it is possible to partition the graph into exactly two connected components by removing a single edge.

More formally, you are given an undirected graph \(G=(V,E)\) with \(|V| = N\) and \(|E| = M\). Check if there exists an edge \((u,v)\) such that after removing it, the resulting graph has exactly two connected components.

If removing an edge results in more than two connected components or the graph remains fully connected, output NO. Otherwise, output YES.

inputFormat

The first line contains two integers \(N\) and \(M\) separated by a space, where \(N\) is the number of nodes and \(M\) is the number of edges in the graph.

The following \(M\) lines each contain two integers \(u\) and \(v\), denoting an undirected edge between nodes \(u\) and \(v\). It is guaranteed that the graph is initially connected.

outputFormat

Output a single line containing either YES or NO. Output YES if it is possible to partition the graph into exactly two connected components by removing one edge, otherwise output NO.

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

YES