考虑若干个能被 \(1\) 到达且能到达 \(1\) 的环，设它们的环长分别为 \(a_1, a_2, ..., a_k\)。
那么我们现在要每个环走若干遍，使得步数不含除 \(2\) 或 \(5\) 以外的质因子。
设第 \(i\) 个环走 \(x_i\) 遍，那么其实就是要求 \(\sum\limits_{i = 1}^k a_i x_i = 10^{10^{100}}\)。
根据裴蜀定理，要求 \(\gcd(a_1, a_2, ..., a_k)\) 不含除 \(2\) 或 \(5\) 以外的质因子。
于是问题转化成求所有环长。
考虑 dfs 树，每一条非树边都对应一个环，找非树边即可。
时间复杂度 \(O(n \log n)\)，瓶颈在求 \(\gcd\)。
加强版是 CF1515G Phoenix and Odometers。
code
// Problem: G - Return to 1
// Contest: AtCoder - Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306）
// URL: https://atcoder.jp/contests/abc306/tasks/abc306_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
int n, m, d[maxn], g;
bool vis[maxn], mk[maxn];
vector<int> G[maxn], T[maxn];
void dfs(int u) {
mk[u] = 1;
for (int v : T[u]) {
if (!mk[v]) {
dfs(v);
}
}
}
void dfs2(int u) {
vis[u] = 1;
for (int v : G[u]) {
if (!mk[v]) {
continue;
}
if (!vis[v]) {
d[v] = d[u] + 1;
dfs2(v);
} else {
int t = abs(d[u] + 1 - d[v]);
g = __gcd(g, t);
}
}
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
vector<int>().swap(G[i]);
vector<int>().swap(T[i]);
d[i] = 0;
vis[i] = mk[i] = 0;
}
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
G[u].pb(v);
T[v].pb(u);
}
g = 0;
dfs(1);
dfs2(1);
if (!g) {
puts("No");
return;
}
while (g % 2 == 0) {
g /= 2;
}
while (g % 5 == 0) {
g /= 5;
}
puts(g == 1 ? "Yes" : "No");
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}