In this problem, we are given a directed graph and asked $q$ queries for the minimum distance between two vertices $u$ and $v$.

Main Idea

The graph is a functional graph, so break it into tree / cycle cases and solve each one independently.

Structure of the Graph

While the graph given in the statement can be modeled as a directed graph, we can be more specific. Since each vertex has one outgoing edge, the resulting graph is a Functional Graph.

An important property of a functional graph is that it's structure is composed of many trees directed towards the root, and a single cycle composed of the roots. So, we can break the graph into two cases.

Tree Case

The first case is if $u$ and $v$ are on the same tree. To check this, we can store the root of the tree that each vertex is on in functional graph, and check if the roots for $u$ and $v$ are equal.

If they are, the problem reduces to finding the distance between two vertices on a tree, which equals $dept{h}_u+dept{h}_v-2\cdot dept{h}_{lca(u,v)}$ where $lca(a,b)$ denotes the lowest common ancestor of vertices $a$ and $b$ and $dept{h}_x$ denotes the distance from the vertex to the root of its tree. If you don't know how to compute $lca$, read Binary Jumping.

Cycle Case

Technically, there are 3 more cases, but they can be solved in the same way so we will group them together. The cycle case is when you need to cross the cycle to go from one vertex to another.

The three situations where this occurs are:

• One vertex is on a tree, and the other is on the cycle.
• Both vertices are on the cycle.
• Both vertices are on trees, but they have different roots.

In all 3 cases, the distance can be computed the same way as $dept{h}_u+dept{h}_v+dis{t}_{r_u,r_v}$ where $r_x$ denotes the root of the tree $x$ is on. Note that if a node is on a cycle, it is the root of its tree. To compute the distance between roots, we can give an arbitrary vertex value $0$ and increase the value as you go around the cycle, similar to how you compute its length in the Functional Graph article.

Then, the distance between two roots is $min(len-(va{l}_u-va{l}_v),va{l}_u-va{l}_v)$ where $len$ is the length of the cycle and $va{l}_u>va{l}_v$, representing going from $u$ to $v$ in either direction.

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;