Rada and the Chamomile Valley

The Smeshariki can take any path from $1$ to $n$. We need the lanes that appear in all such paths.

That wording is the whole problem. It is not asking about shortest paths. It is not asking about one chosen DFS route. It is asking for edges that are impossible to avoid.

Which edges are definitely used?

Call an edge required if every path from $1$ to $n$ uses it.

First, any required edge must be a bridge.

If an edge lies on a cycle, then after entering one endpoint of the edge, you can go around the rest of the cycle and reach the other endpoint without using that edge. So that edge is bypassable. Bypassable means not guaranteed. Dead.

So required edges are among the bridges.

But not every bridge is required. A bridge somewhere in a side branch does not matter if all paths from $1$ to $n$ stay outside that branch.

For a bridge $e$, removing it splits the graph into two connected components. The bridge is required exactly when vertex $1$ is in one component and vertex $n$ is in the other. Then every $1 \to n$ path must cross the bridge, because there is no other connection between the two sides.

So the first part is:

1. Find all bridges.
2. Keep only bridges that separate $1$ and $n$.

Finding the relevant bridges

Run the standard Tarjan DFS for bridges, rooted at vertex $1$.

For every vertex $v$:

• $tin[v]$ is its DFS entry time.
• $low[v]$ is the smallest $tin$ reachable from $v$ using zero or more DFS-tree edges and at most one back edge.

For a DFS tree edge $v \to to$, it is a bridge iff:

$low[to] > tin[v].$

Because then the subtree of $to$ has no back edge reaching $v$ or anything above $v$.

Since the DFS is rooted at $1$, removing a bridge edge $v \to to$ separates the graph into:

• the DFS subtree of $to$,
• everything else, including vertex $1$.

So this bridge separates $1$ and $n$ iff $n$ is inside the subtree of $to$.

We can check that with exit times. During DFS, compute $tout[v]$ after finishing the subtree. Then $x$ is in the subtree of $v$ iff:

$tin[v] \le tin[x] \le tout[v].$

Thus, for every bridge tree edge $v \to to$, it is required iff:

$tin[to] \le tin[n] \le tout[to].$

That gives the exact set of unavoidable lanes.

If this set is empty, every query answer is $-1$.

Answering nearest required lane queries

Now suppose we have all required edges.

For a query vertex $c$, we need the required edge minimizing:

$\min(\rho(c, a), \rho(c, b))$

for edge $(a,b)$.

That is exactly the shortest distance from $c$ to either endpoint of that edge.

So treat every endpoint of every required edge as a source. If required edge $id$ connects $(u,v)$, initialize both $u$ and $v$ with label:

$(0, id).$

For every vertex, we want the best label:

$(distanceToNearestRequiredEdge, smallestEdgeIndexAmongThose).$

The distance part is normal shortest paths in an unweighted graph. The index part is the tie-break.

The cleanest way is to run Dijkstra with lexicographic labels $(distance, edgeIndex)$:

• smaller distance wins;
• if distances tie, smaller edge index wins.

All graph edges have weight $1$, so this is basically BFS with a tie-break, but Dijkstra avoids fiddly queue-order bugs. At $2 \cdot 10^5$, it is easily fast enough.

When relaxing an edge from $v$ to $to$, the candidate label is:

$(dist[v] + 1, bestEdge[v]).$

Update $to$ if that pair is lexicographically better.

After that, every query is answered in $O(1)$ by printing $bestEdge[c]$.

Why this is correct

A lane is required iff every $1 \to n$ path uses it.

If a required lane were not a bridge, then after removing it the graph would still keep its endpoints connected through another route. Any $1 \to n$ path using that lane could replace the lane by the alternate route, producing a path that avoids it. Contradiction. So every required lane is a bridge.

For a bridge, removing it splits the graph into two components. If $1$ and $n$ are on the same side, then there is a $1 \to n$ path entirely inside that side, so the bridge is not required. If they are on opposite sides, every path from $1$ to $n$ must cross between the two components, and the bridge is the only edge doing that. So it is required.

The DFS bridge test finds exactly the bridges. Rooting at $1$ lets us test whether $n$ is in the child subtree of each bridge, which is exactly the “opposite sides” condition.

For queries, the distance from a vertex to an edge is the minimum distance to either endpoint. Initializing both endpoints of each required edge as sources with distance $0$ makes the shortest-path label at vertex $c$ equal to the minimum distance from $c$ to any required edge. Lexicographic Dijkstra preserves the smallest edge index among equal-distance choices, so the stored edge index is exactly what the statement asks for.

Complexity

For each test case:

• DFS bridge search: $O(n+m)$
• Dijkstra over pairs: $O((n+m)\log n)$
• Queries: $O(q)$

The total input size is $2 \cdot 10^5$, so this fits comfortably. No black magic, just bridges and shortest paths doing their jobs.