然后对于一个从 1 所在分量到 n 所在分量的路径，如果它不经过有权值的 SCC，那么这条路径显然对答案不产生贡献，否则同样由裴蜀定理，它的周期是经过的所有 SCC 的权值的 \gcd，而它的相位（也即 x \equiv a \bmod r 中的 a）可以通过经过的跨 SCC 的路径的长度和求得。
由于题目中保证了环长不超过 100，因此有 a < b \le 100，所以可能的 (a,b) 数量可以接受，那么所有路径的 (a,b) 可以在 DAG 上容易求得，注意在遇到第一个有权值的 SCC 之前的状态需要特殊考虑，可以先将所有的模数的情况都求一遍并给每个 SCC 对应模数的情况作为初始值。
那么现在求出了所有的 (a,b)，将相同的 a 的数对合并成为一个周期为 a 的串，需要求的其实就是所有的这些周期串的并的最小周期。发现取并不是很优美，可以取反后改为取交，这样就等于是一个 CRT 合并求解的过程，只是每个同余方程不要求余数等于特定值而要求属于一个集合，但本质是差不多的。下面的讨论一律按照取交写，称最后取交后的串为最终串，不难发现最终串其实就是这个 CRT 的解集。
首先先给每个串求出最简周期，这样处理后所有的周期串都不存在周期。首先考虑所有的 a 两两互质的情况，发现此时答案就是 T = \operatorname{lcm} a，首先不难发现 T 一定是答案的倍数，然后考虑如果存在一个长度是 T 的因数且不是 T 的周期，那么一定存在一个 a 不是这个周期的因数，那么由于这个周期串没有周期，所以这个小于 T 的周期一定会因此不成立。
那么现在考虑一般情况怎么变成一个全部互质的情况，考虑如果先枚举一个数 x 并只考虑最终串中所有模一个常量 C 余 x 的位置，那么此时一个长度为 a 的周期就变成了一个长度为 \dfrac a{\gcd(a,B)} 的周期。那么如果这时的所有周期两两互质并且没有一个全 0 的周期序列让解集为空集，那么我们就可以将每个周期对应的 1 的位置标位合法了，因为它们都可以在这个同余的集合中找到一个解。