这是一个在有向图中寻找两个点在环上相遇的最小步数问题。由于每个点只有一条出边，整个图由若干棵基环树组成。

算法思路

核心思想

1. 基环树识别：通过拓扑排序找出所有环
2. 环上处理：为每个环分配ID，记录环长和每个节点在环上的位置
3. 树链处理：对环外的树部分进行DFS，记录深度和根节点（环上的点）
4. LCA查询：如果两个点在同一棵基环树的树部分，用LCA求距离
5. 环上相遇：如果两个点在不同环或同一环的不同位置，计算环上最短路径

关键步骤

1. 基环树分解

// 拓扑排序找环
for(int i=1;i<=n;i++) if(!in[i]) q[++t]=i;
while(h<t){
    h++; int u=q[h];
    int v=f[u][0]; in[v]--;
    if(!in[v]) q[++t]=v;
}

2. 环信息记录

void doit(int u,int id,int az){
    tree[u]=id;           // 环ID
    len[id]++;            // 环长
    step[u]=az;           // 环上位置
    doit(f[u][0],id,az+1);
}

3. 分类处理查询

• 情况1：在不同环 → 输出 -1 -1
• 情况2：在同一基环树的树部分 → LCA求距离
• 情况3：在同一环的不同位置 → 计算环上最短路径

4. 环上路径计算

int ans1=de[u]+(step[r2]-step[r1]+len[tree[r1]])%len[tree[r1]];
int ans2=de[v]+(step[r1]-step[r2]+len[tree[r1]])%len[tree[r1]];

时间复杂度

• 预处理：$O(n \log n)$（LCA预处理）
• 查询处理：$O(\log n)$ 每次查询
• 总复杂度：$O((n+m) \log n)$