1234567890sjx @ 2024-11-26 22:35:29
rt,萌新真的不知道哪里有问题了/kel
bool beginmem;
pair<signed, signed> edge[N];
vector<pair<signed, signed>> z[100100];
signed deg[N], n, m, vis[N];
int buc[N];
inline int binom2(int x) {
return x * (x - 1) / 2;
}
map<pair<signed, signed>, int> id;
int cycle_3() {
fill(deg + 1, deg + n + 1, 0ll);
for (int i = 1; i <= m; ++i) {
int x = edge[i].first, y = edge[i].second;
++deg[x], ++deg[y];
edge[i] = {x, y};
}
for (int i = 1; i <= n; ++i) z[i].clear();
for (int i = 1; i <= m; ++i) {
int x = edge[i].first, y = edge[i].second;
if (deg[x] < deg[y] || deg[x] == deg[y] && x < y) z[x].eb(y, i);
else z[y].eb(x, i);
}
int cnt = 0;
for (int i = 1; i <= n; ++i) {
for (auto &j : z[i]) vis[j.first] = 1;
for (auto &j : z[i]) for (auto &k : z[j.first])
if (vis[k.first]) ++cnt, ++buc[j.second], ++buc[k.second], ++buc[id[{i, k.first}]];
for (auto &j : z[i]) vis[j.first] = 0;
}
for (int i = 1; i <= n; ++i) z[i].clear(), z[i].shrink_to_fit();
return cnt;
}
void run() {
while (scanf("%d%d", &n, &m) == 2) {
id.clear();
fill(buc + 1, buc + m + 1, 0ll);
for (int i = 1; i <= m; ++i)
edge[i].first = read(), edge[i].second = read(), id[{edge[i].first, edge[i].second}] = id[{edge[i].second, edge[i].first}] = i;
cycle_3();
int cnt = 0;
for (int i = 1; i <= m; ++i) cnt += binom2(buc[i]);
cout << cnt << '\n';
}
}
bool endmem;