题意简述

对于一个无向图 $G$ 中的任意一对节点 $u,v$，若存在另一对不同的节点 $x,y$ 使得 $(u, x),(u, y),(v, x), (v, y) \isin E$，则 $(u, v) \isin E$。

现在给你一个不再能通过上面操作建立新边的图 $G$，需要你算出在去掉最多多少条连边之后的图 $G'$，仍能够不断通过上面的操作回到 $G$ 状态。

思路

令建立新边的操作为“长（zhǎng）边”。

:::info[问题 1]{open} 首先我们思考哪些边会是能够删除的。（能不能选择，不是会不会选择） :::

:::success[答案 1] 不难发现，所有处于原图的子图且该子图为完全图（但是节点个数要多于 $3$）的时候，这个边能删。 :::

:::warning[证明 1] 首先，根据题目条件，我们知道，如果 $4$ 个节点 $a, b, c, d$ 他们是与某一次长边有关的 $4$ 个节点，那么他们必然发展成一个 $4$ 节点完全图。

也就是说，我们要删边说明要能长边，要能长边说明一定在一个 $4$ 节点完全图中。

我们接着拓展情况，加入 $e$ 节点，假如某一次长边与 $b, c, d, e$ 有关，那么根据上述推导，能说明 $b, c, d, e$ 在一个 $4$ 节点完全图中。也就是说，$e$ 至少与 $b, c$ 连边，也就是说，根据长边的规则，$e$ 也一定与 $a$ 连边，因此 $a, b, c, d, e$ 构成的图一定是一个 $5$ 节点完全图。

根据数学归纳法，我们能够推出：能够删的边，一定存在于完全图中。 :::

根据这个点，我们只需要看图中的所有完全子图就好了。

但是这些边，不是所有都能够选的，它们存在一些制约限制。比如说，我们不能删掉一个点与这个图的所有连边，剩 $1$ 个也不行。

那怎么办呢？

对于每一个完全子图，它内部的删边的方式与节点的编号应该是无关的。比如，对于一个由节点 $1, 2, 3, 4$ 组成的完全图，你如果只删除 $1$ 条边的话，对于删除 $(1, 2)$ 还是 $(3, 4)$ 是没有区别的。

也就是说，对于相同节点数量的完全图，能去掉的最多边数一定是定值。

:::info[问题 2]{open} 在一个有 $k$ 个节点完全图中（$k \ge 4$），最少需要保留多少条“骨架边”，仍能通过长边复原？ :::

:::success[答案 2] 留下 $\left\lceil \frac{3k}{2} \right\rceil - 2$ 条边。 :::

:::warning[证明 2] 最基础的是 $4$ 个节点的 $4$ 元环（它是从 $4$ 节点完全图中删边得到的最少边的图），这个读者自证不难。

从感性理解的角度来说，我们不断加点，形成新的 $3$ 元环或者 $4$ 元环（这样才能够在长边之后成为完全图），形成 $4$ 元环的最便宜选择就是在 $3$ 元环上加一个点（同时边数只增加 $1$），形成 $3$ 元环的前提条件是不破环原有的 $4$ 元环，那么我们只能把这个节点和两个相邻的节点连边。

也就是说，我们没有 $3$ 元环的时候，使用增加 $1$ 个节点与 $2$ 条连边的代价增加一个 $3$ 元环最优（无论是当下还是对未来）。有 $3$ 元环的时候，使用增加 $1$ 个节点与 $1$ 条连边的代价增形成一个 $4$ 元环最优（无论是当下还是对未来）。

也就是说，我们增加的边数是 $+2,+1,+2,+1 \cdots$ 的一个数列。

进而推出结论：留下 $\left\lceil \frac{3k}{2} \right\rceil - 2$ 条边。

取上整是因为边数是先 $+2$ 再 $+1$，即从偶数个节点变为奇数个节点时 $+2$ 条边，从奇数个节点变为偶数个节点时，$+1$ 条边。 :::

那么，接下来的操作，就是统计每个完全子图的节点个数再进行计算了。

这里我想到了一个神秘做法，当然基于上面的推导读者应该也能够产生自己的做法。

我本来是想着用并查集维护点的，但我注意到两个极大的完全子图如果有一个公共点的话，那它们就被合并了（即统计答案的时候会少 $+2$ 条边），于是我使用并查集维护。

当我们发现 $3$ 元环（也就是 $3$ 节点完全子图）的时候，就把它的每一条边加入并查集。

由于是完全子图，我们只需要找 $cnt_e \ge 6$ 的并查集即可（因为 $4$ 节点完全图为 $6$ 条边）。

:::warning[正确性证明] 从完全图本身看

完全图内任意三点一定有互相连边，因此，成为一个三元环的三条边至少会是在一个完全图中。

同时，又由于一条边可能不只是出现一个三元环中，它会出现在 $(n - 2)$ 个三元环当中（$n$ 为子图节点个数），因此，可以由这条边合并所有在同一完全子图中的其他的边。

从其他的边看

• 如果外围是有一个完全图共节点，那么与我们正在考虑的完全图只会有一个节点公共，也就是说，在这两个完全图之间无法形成三元环。

• 如果外围是一个不重要的图共节点，那么能够合并进来形成更大的的完全子图的，一定只有加三元环或四元环，更大的环是不可能的，因为连接的两个任意的公共点在环上的剩余部分一定无法连接到同一个节点，因此长不出公共边。而又由于题目给的图是确保了长边操作进行了足够多次的，所以 $4$ 元环的可能也被我们排除。

  （这里首先排除链状结构是因为链状结构不会产生两个公共点，没有一种链状结构会满足长边的条件） :::

Code

/*
 * @file P17166.cpp
 * @author Federico Prask
 * @date 2026-07-29
*/

#include <bits/stdc++.h>

#define file(s) \
	std::freopen(#s".in", "r", stdin), std::freopen(#s".out", "w", stdout)

using i64 = long long;
using ull = unsigned long long;
using i28 = __int128;
using f32 = double;
using ldb = long double;

constexpr int N = 1005;
constexpr int M = 500005;

struct DisjointSetUnion {
	int fa[M];
	int sz[M];
	
	void init(int n) {
		for (int i = 1; i <= n; i++) {
			fa[i] = i;
			sz[i] = 1;
		}
	}
	
	int find(int x) {
		if (fa[x] == x) {
			return x;
		}
		return fa[x] = find(fa[x]);
	}
	
	bool merge(int x, int y) {
		int sx = find(x);
		int sy = find(y);
		if (sx != sy) {
			if (sz[sx] < sz[sy]) {
				std::swap(sx, sy);
			}
			fa[sy] = sx;
			sz[sx] += sz[sy];
			return true;
		}
		return false;
	}
};

DisjointSetUnion dsu;

struct Edge {
	int to, next;
};

int num, head[N];
Edge e[M << 1];

void add_edge(int from, int to) {
	e[++num] = {to, head[from]};
	head[from] = num;
}

int eid[N][N];

inline int read() {
	register int x = 0, sign = 1;
	register char ch = getchar_unlocked();
	for (; !isdigit(ch); ch = getchar_unlocked()) {
		if (ch == '-') {
			sign = -1;
		}
		if (ch == EOF) {
			return EOF;
		}
	}
	for (; isdigit(ch); ch = getchar_unlocked()) {
		x = x * 10 + ch - '0';
	}
	return x * sign;
}

void work() {
	int n = read(), m = read();
	dsu.init(m);
	for (int i = 1; i <= m; i++) {
		int u = read(), v = read();
		if (eid[u][v] == 0) {
			eid[u][v] = eid[v][u] = i;
			add_edge(u, v), add_edge(v, u);
		}
	}
	for (int u = 1; u <= n; u++) {
		for (int i = head[u]; i; i = e[i].next) {
			int v = e[i].to;
			if (u < v) {
				int e1 = eid[u][v];
				for (int w = 1; w <= n; w++) {
					if (eid[u][w] != 0 && eid[v][w] != 0) {
						dsu.merge(e1, eid[u][w]);
						dsu.merge(e1, eid[v][w]);
					}
				}
			}
		}
	}
	i64 ans = 0;
	for (int i = 1; i <= m; i++) {
		if (dsu.find(i) == i) {
			i64 sz = dsu.sz[i];
			i64 k = (1 + std::sqrt(1 + 8 * sz)) / 2;
			if (k >= 4) {
				i64 lft = (3 * k + 1) / 2 - 2;
				ans += (sz - lft);
			}
		}
	}

	printf("%lld\n", ans);
}

int main() {
	#ifndef ONLINE_JUDGE
	file();
	#endif
	
	#ifdef CPPIO
	std::cin.tie(0) -> sync_with_stdio(0);
	#endif

	work();

	return 0;
}