James and the Chase

Observation 1: testing one root is actually easy

Take a candidate root $s$ and run a DFS from it. Let the DFS tree be the parent tree.

Claim:

$$s \text{ is interesting } \iff \text{ every edge is either a tree edge or goes to an ancestor in this DFS tree.}$$

Why?

• If there is an edge $u \to v$ which is not a tree edge and $v$ is not an ancestor of $u$, then the tree path $s \rightsquigarrow u$ plus the edge $u \to v$ gives another simple path from $s$ to $v$. Boom, uniqueness is dead.
• Conversely, if every non-tree edge goes to an ancestor, then a simple path from $s$ cannot use any non-tree edge at all: such an edge jumps to a vertex already lying on the current path from $s$, so the path would repeat a vertex and stop being simple. Therefore every simple path from $s$ is forced to use only tree edges, so the tree path is the unique simple path to every vertex.

So one candidate can be checked in $O(n+m)$ using DFS order and ancestor checks.

That part is the easy one. The annoying part is: how do we find such a root?

Observation 2: the $20\%$ condition is begging for randomization

If there are at least $n/5$ interesting vertices, then a uniformly random vertex is interesting with probability at least $1/5$.

So if we try $K$ random vertices, the probability of missing all interesting ones is

$$\left(\frac45\right)^K.$$

With $K=80$ this is below $2\cdot 10^{-8}$. Basically: if you still miss, the universe personally hates you.

So:

1. Shuffle the vertices.
2. Check the first $\min(n, 80)$ of them.
3. If none works, print $-1$.

This is exactly why the problem has the probabilities tag. It is not there for decoration.

Observation 3: fix one interesting root $r$

Now suppose we found one interesting root $r$. Run DFS from $r$ and get its tree $T$.

Because $r$ is interesting, every edge is either:

• a tree edge, or
• a back edge from a vertex to one of its ancestors.

Now take some other vertex $u \ne r$.

What can a simple path starting from $u$ look like?

• As long as it uses tree edges, it stays inside $subtree(u)$.
• If it ever wants to leave $subtree(u)$, it must use a back edge from some vertex $x \in subtree(u)$ to a strict ancestor of $u$.
• It can use at most one such back edge. After one upward jump, any second upward jump would go to a vertex already on the path, so the path would no longer be simple.

This completely kills the complexity of the problem.

Observation 4: exact characterization of interesting vertices

For $u \ne r$, the vertex $u$ is interesting iff among all back edges with source in $subtree(u)$:

• there is exactly one edge whose target is a strict ancestor of $u$, and
• that unique edge goes to $r$.

Why is this necessary?

• If there is no such edge, $u$ cannot reach $r$ at all.
• If the unique such edge goes to some ancestor $a \ne r$, then after jumping to $a$ you can only go down using tree edges, so $r$ is still unreachable.
• If there are at least two such edges, uniqueness dies:
  • two edges to $r$ give two paths to $r$;
  • one edge to $r$ and one to another ancestor $a$ give two paths to $a$;
  • if none goes to $r$, again $r$ is unreachable.

Why is it sufficient?

• Any path from $u$ to a vertex inside $subtree(u)$ must stay entirely inside $subtree(u)$, hence it is the unique tree path.
• Any path from $u$ to a vertex outside $subtree(u)$ must leave via a back edge to a strict ancestor of $u$. There is exactly one such edge, and it goes to $r$, so the whole path is forced:

$$u \rightsquigarrow x \to r \rightsquigarrow v.$$

No choices, no drama, no extra paths.

Observation 5: turn that condition into subtree DP

We only need two subtree aggregates.

1. Count edges to the root

Let

$$cnt[u] = \#\{x \to r \mid x \in subtree(u)\}.$$

This is the number of back edges from $subtree(u)$ directly to $r$.

2. Track the shallowest non-root back-edge target

Let

$$mn[u] = \min depth(v)$$

over all back edges $x \to v$ with $x \in subtree(u)$ and $v \ne r$.

If no such edge exists, set $mn[u] = +\infty$.

Then for $u \ne r$:

$$u \text{ is interesting } \iff cnt[u] = 1 \text{ and } mn[u] \ge depth[u].$$

Why does the $mn$ condition work?

• A non-root back edge from $subtree(u)$ to a vertex of depth $< depth[u]$ goes to a strict ancestor of $u$, which is forbidden.
• If every non-root back edge has target depth $\ge depth[u]$, then all those targets stay inside $subtree(u)$, so they do not help leave the subtree and do not create extra simple paths from $u$.

How to compute $cnt$ and $mn$

Scan all edges once.

For each non-tree edge $x \to v$:

• if $v = r$, do $cnt[x]++$;
• otherwise do $mn[x] = \min(mn[x], depth[v])$.

Then process the DFS tree in reverse order (postorder-ish) and merge children into parents:

$$cnt[parent] += cnt[child], \qquad mn[parent] = \min(mn[parent], mn[child]).$$

Finally:

• $r$ itself is interesting;
• every other vertex $u$ is interesting iff $cnt[u]=1$ and $mn[u] \ge depth[u]$.

If the number of interesting vertices is $k$ and

$$5k < n,$$

print $-1$, otherwise print them in increasing order.

Complexity

One root check is $O(n+m)$.

We do at most $80$ random checks, so the randomized search is

$$O(80\cdot(n+m)) = O(n+m)$$

with a constant factor. After finding one interesting root, the final subtree DP is another $O(n+m)$.

So the whole solution is linear per test case up to a small constant:

$$O(n+m).$$

And yes, for a $3000$ this one is surprisingly clean once you spot the structure. Before that, it's just graph-shaped pain.