You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
92 lines
2.1 KiB
C++
92 lines
2.1 KiB
C++
#include <cctype>
|
|
#include <cstdio>
|
|
#include <map>
|
|
typedef long long int64;
|
|
const int64 mod = 989381;
|
|
const int maxn = 500010;
|
|
inline void readInt(int &x)
|
|
{
|
|
int ch = x = 0;
|
|
bool F = false;
|
|
for (; !isdigit(ch = getchar()); F = (ch == '-'))
|
|
;
|
|
for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
|
|
F && (x = -x);
|
|
}
|
|
int fa[maxn], cnt[maxn], deg[maxn], head[maxn], to[maxn << 1], next[maxn << 1], idx, n, m, num;
|
|
bool vis[maxn];
|
|
std::map<int, bool> M[maxn];
|
|
int Find(int x) { return x == fa[x] ? x : fa[x] = Find(fa[x]); }
|
|
void link(int x, int y)
|
|
{
|
|
int fx = Find(x), fy = Find(y);
|
|
if (fx != fy)
|
|
{
|
|
fa[fx] = fy;
|
|
cnt[fy] += cnt[fx];
|
|
cnt[fx] = 0;
|
|
}
|
|
}
|
|
inline void addEdge(int x, int y)
|
|
{
|
|
idx++;
|
|
to[idx] = y;
|
|
next[idx] = head[x];
|
|
head[x] = idx;
|
|
}
|
|
int fast_pow(int64 base, int pow)
|
|
{
|
|
int ans = 1;
|
|
for (; pow; base = (base * base) % mod, pow >>= 1)
|
|
if (pow & 1)
|
|
ans = (ans * base) % mod;
|
|
return ans;
|
|
}
|
|
void dfs(int id, int f)
|
|
{
|
|
num++;
|
|
vis[id] = true;
|
|
if (num > n) return;
|
|
for (int cur = head[id]; cur; cur = next[cur])
|
|
if (to[cur] != f)
|
|
dfs(to[cur], id);
|
|
}
|
|
bool check()
|
|
{
|
|
for (int i = 1; i <= n; i++)
|
|
if (deg[i] > 2) return false;
|
|
for (int i = 1; i <= n; i++)
|
|
if (!vis[i])
|
|
if (deg[i] == 1)
|
|
dfs(i, 0);
|
|
else if (deg[i] == 0)
|
|
vis[i] = true, num++;
|
|
return num == n;
|
|
}
|
|
int main()
|
|
{
|
|
for (int i = 0; i < maxn; i++) fa[i] = i, cnt[i] = 1;
|
|
readInt(n), readInt(m);
|
|
for (int i = 0, x, y; i < m; i++)
|
|
{
|
|
readInt(x), readInt(y);
|
|
if (M[x][y] || M[y][x]) continue;
|
|
addEdge(x, y), addEdge(y, x);
|
|
deg[x]++, deg[y]++;
|
|
link(x, y);
|
|
M[x][y] = M[y][x] = true;
|
|
}
|
|
int64 ans = 0;
|
|
if (check())
|
|
{
|
|
ans = 1;
|
|
int l = 0, p = 0;
|
|
for (int i = 1; i <= n; i++)
|
|
if (fa[i] == i)
|
|
(cnt[i] > 1 ? l : p)++;
|
|
for (int i = 1; i <= l + p; i++) ans = (ans * i) % mod;
|
|
ans = (ans * fast_pow(2, l)) % mod;
|
|
}
|
|
printf("%lld", ans);
|
|
return 0;
|
|
} |