题解：魂灵之影
喵仔牛奶
·
·
题解
闲话：这题是 FAOI R6 原来的 C 题，5.5 交审，然后撞了 5.25 图灵杯的题 :(
Solution
特判掉边权全为 0 的情况。求出所有边权值的 \gcd，记为 D，将所有边权值除以 D。一条路径的真实路径为这种情况下的长度乘以 D。
由于一个环走 z 次长度为 0，我们可以经过任意一个环任意次（经过一个环 z 次，然后在途中插入另一个环）。记所有环长度和的 \gcd 为 d，那么根据裴蜀定理，如果存在一条长度为 p 的路径，一定存在一条长度为 p\bmod\gcd(d,z) 的路径。
考虑求出 d。由于 \gcd(2w_1,2w_2,c\dots,2w_m)=2，d\mid 2。因此，如果存在长度为奇数的环，d=1，否则 d=2。将长度为偶数的边的两端合并为同一个点，如果不是二分图，说明存在长度为奇数的环。
我们求出了 d，考虑询问如何解决。分类讨论：
-
-
- 若 $x,y$ 在同一部分，它们之间所有路径长度为偶数，模 $\gcd(d,z)$ 显然为 $0$，答案为 $0$。
- 若 $x,y$ 不在同一部分，它们之间所有路径长度为奇数，若 $\gcd(d,z)=1$，答案为 $0$。否则，路径的真实长度为 $D+2Dx$（$x$ 可以为任意非负整数）。根据裴蜀定理，答案即为 $D\bmod\gcd(2D,z)$。
复杂度 \mathcal O(n+m+q\log V)。