我们沿用样例解释中的记号。不难发现，合法方案中所有训练构成的大集合总是可以被划分为若干个形如 $\{(a_1,a_2),(a_2,a_3),\ldots,(a_{2k},a_1)\}$ 的小集合。

如果我们把 $(x,y)$ 看成无向边，那么题面可以抽象为一张 $n$ 个结点 $m$ 条边的无向图，我们需要加上最少的边数使其成为若干个偶数长度环的叠加（可以不是简单环）。

注意到每个环会给环上的结点贡献 $2$ 点度数，因此目标状态中所有点的度数都为偶数，而这样（奇点个数为 $0$）的连通图（要分连通块处理！！！）必定存在欧拉回路。当总边数为偶数时，欧拉回路本身就是一个偶数长度环，满足要求。

基于这一事实，我们只需要给所有度数为奇数的点连边即可（连边数为奇点数的一半）。

由于上面的结论要求总边数为偶数，边数之和为奇数的连通块也需要连边。（可以证明，将边数之和为奇数的连通块看成单个点时，将这些点连成一个环一定是最优的，此时连边数等于连通块的个数）。

特别地，我们可以在每个存在奇点的连通块中选定两个特殊奇点 $p,q$，然后连边 $(p_1,q_2),(p_2,q_3),\ldots,(p_l,q_1)$，把这些连通块连通。这一做法可以最小化边数之和为奇数的连通块个数。

#include <bits/stdc++.h>
using namespace std;
struct R
{
    int ld[100012];
    stack<pair<int, int> > rec;
    void init(int n)
    {
        for (int i = 1; i <= n; i++)
            ld[i] = i;
    }
    int get(int x)
    {
        if (ld[x] == x) return x;
        ld[x] = get(ld[x]);
        return ld[x];
    }
    void mrg(int x, int y)
    {
        x = this -> get(x), y = this -> get(y);
		if (x > y) swap(x, y);
        ld[y] = x;
    }
};
R r;
int dc[100012], ec[100012], x[100012], y[100012];
signed main()
{
	int n, m;
	cin >> n >> m;
	r.init(n);
	for (int i = 1; i <= m; i++)
	{
		cin >> x[i] >> y[i];
		dc[x[i]]++, dc[y[i]]++;
		r.mrg(x[i], y[i]);
	}
	for (int i = 1; i <= n; i++)
	{
		if (dc[i] & 1) ec[r.get(i)]++;
		if (r.get(i) != i) dc[r.get(i)] += dc[i], dc[i] = 0;
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		ans += ec[i] / 2;
		if (ec[i] == 0 && (dc[i] & 2)) ans++;
	}
	if ((ans + m) & 1) ans++;
	cout << ans << endl;
 	return 0;
}