1731. Is This Link Fragile

An UNDIRECTED graph has n vertices and m edges. For EACH edge, in the order it was listed, print Yes if that edge is a bridge and No if it is not. An edge is a bridge when deleting it leaves some pair of vertices with no path between them.

Print None when m is 0, so that the output is never an empty line.

1-2, 2-3 -> Yes Yes 1-2, 1-2 -> No No 1-2, 2-3, 3-2 -> Yes No No 1-1 -> No

## Why answering per edge rather than per bridge

Two reasons, and both are about the cases a count or a sorted list hides.

A self-loop and a parallel edge are both answered No, and a solution that collects bridges into a set and prints the set never has to decide what to do with them. Walking the input edge by edge forces an answer for every single edge, including the ones the search skipped entirely.

And in the third example above, 2-3 and 3-2 are the same pair of vertices written both ways round. Neither is a bridge, because they protect each other, and a solution keying edges by their endpoint pair would treat them as one edge and report Yes.

## The three things that have to be said

directed? no, so 2-3 and 3-2 are the same edge. self-loops? allowed, and the answer is always No. parallel edges? allowed, and the answer is always No for every copy. disconnected? allowed. An edge can only be a bridge within its own piece.

## What most people try first

Removing each edge and recounting the pieces. Correct, O(m(n + m)), and at n = m = 200000 that is 8 * 10^10 steps.

The second attempt is to run problem 1730 and look each input edge up in the result. That works, and it is worth noticing that the lookup has to be by edge NUMBER: looking up by endpoint pair reintroduces exactly the bug the third example is built to catch.

## The method

Run the undirected low-link search of problem 1728, keeping for each vertex the INDEX of the edge the search arrived by. Mark an array of m booleans:

isBridge = m copies of false for every v with a parent: if low[v] > tin[par[v]]: isBridge[pe[v]] = true then print isBridge[0..m-1], one per line, as Yes or No

Everything not marked is No, which is what gives self-loops, parallel edges and non-tree edges their answer with no special case at all. That is the point of the boolean array: it answers for edges the search never considered.

## Why that is right

A depth-first search of an undirected graph has no cross edges: every non-tree edge joins a vertex to one of its own ancestors. So the only routes out of v's subtree are the tree edge up to par[v] and the non-tree edges from inside the subtree to ancestors, and low[v] is exactly the earliest entry time those offer. If low[v] > tin[par[v]] nothing reaches par[v] or above and the tree edge is the only route, so it is a bridge; otherwise a second route exists. A non-tree edge always has the tree path between its ends as a second route, so it is never a bridge.

## Cost

Time O(n + m log m), space O(n + m). The search is ITERATIVE: a path of 200000 vertices is permitted and recursion on it overflows Python's recursion limit and the default stack in C, C++ and Java.

## Related

Problem 1729 counts them and problem 1730 lists them. Problem 1738 asks how much damage the worst bridge does, and problem 1735 asks what the graph breaks into when they all go at once.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, so self-loops can occur - the same pair may be listed more than once, in either order, so parallel edges can occur - the graph may be disconnected