CF1835D Doctor's Brown Hypothesis

由于 \(k\) 够大，你可以随便在图上走环，不用担心不用走，那么你所担心的只有环长的 \(\rm gcd\)。

将所有强连通分量先求出，满足条件的点对必然在一个强连通分量里。我们以随便一个点为根，跑出强连通分量中的一棵dfs树，我们断言，如果 \(dep_x-dep_y \equiv dep_y-dep_x \equiv k \bmod d\)，\(d\) 是强联通分量内的所有环长的 \(\rm gcd\)，则 \((x,y)\) 满足条件。为什么距离可以直接写为深度相减？因为这是一个强连通分量，它的dfs树必然长成一个链的样子。

既然都是个链了，那环长就是 \(|dep_v-dep_u-1|\)。证明：对于返祖边是显然的，对于前向边，因为一定存在 \(v\) 到 \(u\) 的环，我们将这个环绕 \(d\) 次,每次绕到 \(u\) 直接走前向边，最后一次走树边，那就多走了 \(dep_v-dep_u-1\) 步，证毕。

我们把 \(d\) 求出后，根据我们的式子，解出 \(k \equiv 0 \bmod d\) 或 \(k \equiv \frac{d}{2} \bmod d,d \equiv 0 \bmod 2\)。判完后，简单计数即可。