#include <bits/stdc++.h>

class Edge
{
public:
    int to;
    int next;
    int color = -1;
};

Edge edges[200020];
int  heads[200020];
bool visited[200020];

auto cnt = 0;
void add(int u, int v)
{
    edges[++cnt].to = v;
    edges[cnt].next = heads[u];
    heads[u]        = cnt;
}

auto color_0 = 0, color_1 = 0;
void dfs(int now)
{
    visited[now] = true;

    if (edges[now].color == 0)
    {
        color_0++;
    }
    else
    {
        color_1++;
    }

    for (auto i = heads[now]; i; i = edges[i].next)
    {        
        if (!visited[edges[i].to])
        { // 一定要在染色前特判！！！（否则如记录一qwq）   
            edges[edges[i].to].color = (1 - edges[now].color);
        } 

        if (edges[edges[i].to].color == edges[now].color)
        { // 一定要在染色后检查！！！（否则如记录二qwq）  
            std::cout << "Impossible" << std::endl;
            exit(0);
        }
        
        if (!visited[edges[i].to])
        {
            dfs(edges[i].to);
        }
    }
}

int n, m, u, v;
int main()
{
    std::cin >> n >> m;
    for (auto i = 1; i <= m; i++)
    {
        std::cin >> u >> v;

        add(u, v);
        add(v, u);
    }

    auto ans = 0;
    for (auto i = 1; i <= n; i++)
    {
        if (!visited[i])
        {
            color_0        = 0;
            color_1        = 0;
            edges[i].color = 0;
            dfs(i);
            ans += std::min(color_0, color_1);
        }
    }

    std::cout << ans << std::endl;

    return 0;
}

记录一

记录二

我怎么这么蒻啊，调了好久qwq