Description：

给一张图，要求你再尽可能的多连边，使得从 $1$ 到 $2$ 至少要经过 $5$ 条边。

$1\leqslant n\leqslant 40000,1\leqslant m\leqslant 10^6$

Solution：

发现最后的情况可以把所有点划分成 $5$ 个集合，分别是 $1$ 所在的集合 $,1,3,4,2,2$ 所在的集合，每个集合是一个完全图，相邻两个集合之间两两有边，考虑怎么构造出这五个集合，首先发现 $1$ 所在的集合一定只有 $1$ ，因为 $1$ 所在集合中的点只能和 $1$ 所在集合中的点和 $1$ 集合连边，这样肯定不如放在 $1$ 集合中，除了上述边还可以和 $3$ 集合中的点连边，然后这样和 $1$ 或 $2$ 有边的点一定被分别分到了 $1$ 和 $2$ ，这时就该考虑和 $1$ 或 $2$ 有边的点该放在哪里，发现如果放在 $1$ 或 $2$ 里，那就可以和 $1$ ， $1$ 集合和 $3$ 集合连边，但是由于集合 $4$ 的大小一定大于等于 $1$ ，所以不如舍弃和 $1$ 的边转而和 $4$ 集合连边，这时还剩一些点，于是就在 $3$ 和 $4$ 中找一个能连最多点的把他们都放进去肯定最优。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 40010

#define MAXM 1000010

struct edge

{

	int to,nxt;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int type[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	int tot1 = 0,tot2 = 0;

	for(int i = lin[1];i != 0;i = e[i].nxt)

	{

		type[e[i].to] = 1;

		++tot1;

	}

	for(int i = lin[2];i != 0;i = e[i].nxt)

	{

		type[e[i].to] = 2;

		++tot2;

	}

	int tot3 = 0,tot4 = 0;

	for(int k = 3;k <= n;++k)

	{

		if(type[k] != 0)continue;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(type[e[i].to] == 0)continue;

			if(type[e[i].to] == 1)++tot3;

			else ++tot4;

			break;

		}

	}

	int rem = n - 2 - tot1 - tot2 - tot3 - tot4;

	if(tot3 > tot4)tot3 += rem;

	else if(tot4 > tot3)tot4 += rem;

	else if(tot1 > tot2)tot3 += rem;

	else tot4 += rem;

	long long ans = 0;

	ans += tot1 * (tot1 - 1) / 2 + tot2 * (tot2 - 1) / 2 + tot3 * (tot3 - 1) / 2 + tot4 * (tot4 - 1) / 2;

	ans += tot1 + tot2 + tot1 * tot3 + tot2 * tot4 + tot3 * tot4;

	cout << ans - m << endl;

	return 0;

}