|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
typedef long long LL;
|
|
|
const int N = 3010, M = N << 4;
|
|
|
|
|
|
const LL mod = 19491001;
|
|
|
// 链式前向星
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
void add(int a, int b, int c = 0) {
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
int n, m;
|
|
|
|
|
|
// 最简并查集
|
|
|
int p[N];
|
|
|
int find(int x) {
|
|
|
if (x == p[x]) return x;
|
|
|
return p[x] = find(p[x]);
|
|
|
}
|
|
|
|
|
|
LL f[N];
|
|
|
|
|
|
int dfn[N], low[N], ts;
|
|
|
int stk[N], top;
|
|
|
int bcnt;
|
|
|
|
|
|
/*
|
|
|
// 边双模板
|
|
|
vector<int> bcc[N];
|
|
|
int dcc[N];
|
|
|
void tarjan(int u, int from) {
|
|
|
dfn[u] = low[u] = ++ts;
|
|
|
stk[++top] = u;
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (!dfn[v]) {
|
|
|
tarjan(v, i);
|
|
|
low[u] = min(low[u], low[v]);
|
|
|
} else if (i != (from ^ 1))
|
|
|
low[u] = min(low[u], dfn[v]);
|
|
|
}
|
|
|
|
|
|
if (dfn[u] == low[u]) {
|
|
|
++bcnt;
|
|
|
int x;
|
|
|
do {
|
|
|
x = stk[top--];
|
|
|
bcc[bcnt].push_back(x); // 记录边双中有哪些点
|
|
|
dcc[x] = bcnt; // 反向记录x这个点在bcnt这个边双里面
|
|
|
} while (x != u);
|
|
|
}
|
|
|
}
|
|
|
*/
|
|
|
int dcc[N]; // 记录每一个节点在哪个边双中
|
|
|
bool vis[M << 1];
|
|
|
void tarjan(int u, int fa) {
|
|
|
low[u] = dfn[u] = ++ts;
|
|
|
stk[++top] = u;
|
|
|
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
if (vis[i]) continue;
|
|
|
if ((i == fa) || ((i ^ 1) == fa)) continue;
|
|
|
int v = e[i];
|
|
|
|
|
|
if (!dfn[v]) {
|
|
|
vis[i] = vis[i ^ 1] = 1;
|
|
|
tarjan(v, fa);
|
|
|
vis[i] = vis[i ^ 1] = 0;
|
|
|
low[u] = min(low[u], low[v]);
|
|
|
} else
|
|
|
low[u] = min(low[u], dfn[v]);
|
|
|
}
|
|
|
if (low[u] == dfn[u]) {
|
|
|
dcc[u] = ++bcnt;
|
|
|
while (stk[top] != u)
|
|
|
dcc[stk[top--]] = bcnt;
|
|
|
top--;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int calc(int u, int v) {
|
|
|
int x = find(u), y = find(v);
|
|
|
if (x != y) return 0;
|
|
|
if (dcc[u] != dcc[v]) return 1;
|
|
|
if (f[u] == f[v]) return 3;
|
|
|
return 2;
|
|
|
}
|
|
|
int main() {
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
freopen("P4214.in", "r", stdin);
|
|
|
#endif
|
|
|
memset(h, -1, sizeof h);
|
|
|
scanf("%d %d", &n, &m); // 节点数和管道数
|
|
|
for (int i = 1; i <= n; i++) p[i] = i; // 初始化并查集
|
|
|
|
|
|
for (int i = 1; i <= m; i++) { // 枚举每条边
|
|
|
int a, b;
|
|
|
scanf("%d %d", &a, &b);
|
|
|
add(a, b), add(b, a);
|
|
|
|
|
|
// 并查集这是在干什么？记录点与点的连通性？
|
|
|
int x = find(a), y = find(b);
|
|
|
if (x != y) p[x] = y;
|
|
|
}
|
|
|
|
|
|
// base case初始化
|
|
|
for (int i = 1; i <= n; i++) f[i] = 1ll;
|
|
|
|
|
|
// 为什么是m+1次呢？
|
|
|
for (int x = 1; x <= m + 1; x++) {
|
|
|
// tarjan初始化
|
|
|
memset(low, 0, sizeof low);
|
|
|
memset(dfn, 0, sizeof dfn);
|
|
|
ts = 0, bcnt = 0, top = 0;
|
|
|
// 跑Tarjan,可能不连通
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
if (!dfn[i]) tarjan(i, x << 1);
|
|
|
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
f[i] = f[i] * mod + (LL)dcc[i];
|
|
|
}
|
|
|
|
|
|
// 根据题意，计算最终的结果
|
|
|
int ans = 0;
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
for (int j = i + 1; j <= n; j++)
|
|
|
ans += calc(i, j);
|
|
|
// 输出
|
|
|
printf("%d\n", ans);
|
|
|
return 0;
|
|
|
} |
