Bridge Detection in Undirected Graph

You are given an undirected graph with \(n\) vertices and \(m\) edges. Your task is to determine if the graph contains any bridges. A bridge is an edge which, when removed, increases the number of connected components in the graph.

You need to implement an algorithm that analyzes the graph and outputs YES if at least one bridge exists, or NO if there are no bridges.

The concept of bridges can be formally defined using discovery and low-link values. Let \(disc[u]\) denote the time when vertex \(u\) is first visited, and let \(low[u]\) be the smallest discovery time reachable from \(u\) (including via back edges). An edge \((u, v)\) is a bridge if and only if:

\(low[v] > disc[u]\)

inputFormat

The first line of input contains two integers \(n\) and \(m\) representing the number of vertices and the number of edges in the graph respectively.

Each of the next \(m\) lines contains two integers \(u\) and \(v\), indicating that there is an undirected edge between vertices \(u\) and \(v\). The vertices are numbered from 1 to \(n\).

outputFormat

Output a single line containing YES if there is at least one bridge in the graph; otherwise, output NO.

4 4
1 2
1 3
2 3
3 4

YES