题目链接点击打开链接题目解法首先只有在一个强联通分量里的点对才可能合法，因此我们这里说的图默认为强联通图但是上面的条件成立只需要满足\(k\gen\)，考虑用好\(k\)可以认为是极大的性质所以说我们可以通过图中所有的环\(+\)路径来凑出\(k\)不难发现，所有的环能构成的

原题翻译好题！图论用数论的解法真的很巧妙首先注意读题，要恰好等于\(k\)，因为我看错了这题有没有边权都是可以做的，为了使这个做法更具普遍性，我们假设原题有边权可以发现对于满足条件的点对\((x,y)\)至少要满足他们在一个强联通分量内，所以我们可以在每一个强联通分量内计算答案

由于\(k\)够大，你可以随便在图上走环，不用担心不用走，那么你所担心的只有环长的\(\rmgcd\)。将所有强连通分量先求出，满足条件的点对必然在一个强连通分量里。我们以随便一个点为根，跑出强连通分量中的一棵dfs树，我们断言，如果\(dep_x-dep_y\equivdep_y-dep_x\equivk\bmodd\)