Description：

给一个图，选出尽量多的长度为二的路径。

$1\leqslant n\leqslant 2\times 10^5$

Solution：

长度为 $2$ 的路径可以看成是中间点向另外两个点连两条边，那么就可以把这两条边看成都属于这一个点，也就是说我们要使得每条边都属于两个端点其中之一，使得有奇数条边属于的点尽量少。

剩下的做法就很神奇了，先随便找出图的一棵生成树，然后给非树边随便定向，通过调整树边来控制每个点的度数。具体做法是 $dfs$ 这棵树，如果当前节点度数为奇数，就把它到父亲的边给它，否则给父亲，这样下来每个联通块最多只会有根节点无法为偶数，一定是最多的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int m,n;

#define MAXN 200010

struct edges

{

	int u,v;

}es[MAXN];

bool tag[MAXN];

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int deg[MAXN];

bool v[MAXN];

int fa[MAXN];

int root;

void dfs(int k)

{

	v[k] = true;

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

	{

		if(v[e[i].to])continue;

		fa[e[i].to] = k;

		dfs(e[i].to);

	}

	if(k == root)return;

	if(deg[k] % 2 == 1)++deg[k];

	else ++deg[fa[k]];

	return;

}

int main()

{

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

	for(int i = 1;i <= n;++i)f[i] = i;

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

	{

		scanf("%d%d",&es[i].u,&es[i].v);

		if(find(es[i].u) != find(es[i].v))

		{

			tag[i] = true;

			f[find(es[i].u)] = find(es[i].v);

			add(es[i].u,es[i].v);

		}

		else

		{

			++deg[es[i].u];

		}

	}

	int ans = 0;

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

	{

		if(!v[i])

		{

			root = i;

			dfs(i);

			ans += deg[i] % 2;

		}

	}

	cout << ans << endl;

	return 0;

}