【题目来源】
https://www.luogu.com.cn/problem/P1330

【题目描述】
曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。
阳光大学的校园是一张由 n 个点构成的无向图，n 个点之间由 m 条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。
询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。

【输入格式】
第一行两个正整数，表示节点数和边数。 接下来 m 行，每行两个整数 u，v，表示点 u 到点 v 之间有道路相连。

【输出格式】
仅一行。如果河蟹无法封锁所有道路，则输出 Impossible，否则输出一个整数，表示最少需要多少只河蟹。

【输入样例一】
3 3
1 2
1 3
2 3

【输出样例一】
Impossible​​​​​​​

【输入样例二】
3 2
1 2
2 3

【输出样例二】
1

【数据范围】
对于 100% 的数据，1≤n≤10^4，1≤m≤10^5，保证没有重边。

【算法分析】
● 二分图的概念：如果无向图 G=(V, E) 的所有点可以分为两个集合 V1，V2，所有边都在 V1 与 V2 之间，且 V1，V2 的内部都没有边，则称 G 是一个二分图。

● 一个图是否为二分图，一般用“染色法”进行判断。染色法的核心思想非常直观：尝试用两种颜色对图中的所有顶点进行着色，并确保‌任何一条边两端的顶点颜色都不相同‌。如果能成功完成着色，则该图是二分图；否则，不是。

● 染色法的染色逻辑
（1）使用两种颜色：颜色 1 和颜色 2。
（2）若当前节点染色为 c，相邻节点必须染为 3^c（即 3-c）。这是因为，3^1=2，3^2=1，故通过异或运算可实现颜色切换。

● 染色法的算法流程通常基于 BFS 或 DFS 实现。
（1）选择一种颜色（如 1）作为起始颜色。
（2）从一个未访问的节点开始，将其染色，然后遍历其所有邻居。
（3）若邻居未染色，则将其染成与当前节点相反的颜色（如 2），并递归（DFS）或入队（BFS）处理。
（4）若邻居已染色，则检查其颜色是否与当前节点相反。若颜色相同，则说明存在奇环，该图不是二分图。

● 树结构天然是二分图
（1）无环性‌：树是无环连通图，因此不可能存在奇数环。
（2）层次结构‌：从任意根节点开始，奇偶层自然形成两个独立集合。
（2）可二染色性‌：树可以用两种颜色进行顶点着色，使得相邻顶点颜色不同。

● 由于树本身是二分图，节点可以染成两种颜色。设树的节点数为 n，其中一种颜色的节点数为 m，若保证增边后的图形仍是二分图，则最大可增加的边数为 m*(n-m)-(n-1)。其中，m*(n-m) 为完全二分图的最大边数 ，n-1 为树的边数。

【算法代码】
本题代码大部分与“AcWing 860：染色法判定二分图”相同。详见：https://blog.csdn.net/hnjzsyjyj/article/details/155323274

#include <bits/stdc++.h>
using namespace std;

const int N=1e4+5;
const int M=1e5+5;
int e[M<<1],ne[M<<1],h[N],idx;
int color[N];
int cnt[3],ans;
int n,m;

void add(int a,int b) {
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

//Dye node u with color c
bool dye(int u,int c) {
    color[u]=c,cnt[c]++;
    for(int i=h[u]; i!=-1; i=ne[i]) {
        int j=e[i];
        if(!color[j]) { //3^1=2,3^2=1
            if(!dye(j,3^c)) return false;
        } else if(color[j]==c) return false;
    }
    return true;
}

int main() {
    memset(h,-1,sizeof h);
    cin>>n>>m;
    while(m--) {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }

    bool flag=true;
    for(int i=1; i<=n; i++) {
        cnt[2]=cnt[1]=0;
        if(!color[i]) {
            if(!dye(i,1)) {
                flag=false;
                break;
            }
        }
        ans+=min(cnt[1],cnt[2]);
    }
    if(flag) cout<<ans<<endl;
    else cout<<"Impossible\n";

    return 0;
}

/*
in:
30 12
18 12
11 5
5 30
15 23
28 2
12 2
3 26
7 28
25 22
4 3
27 22
6 9

out:
7
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/155283857
https://blog.csdn.net/hnjzsyjyj/article/details/155323274
https://blog.csdn.net/hnjzsyjyj/article/details/155244098
https://www.luogu.com.cn/problem/solution/P1330
https://www.cnblogs.com/Shy-key/p/7073662.html
https://www.luogu.com.cn/problem/P10378
https://blog.csdn.net/weixin_51797626/article/details/122650456
https://www.nowcoder.com/discuss/353148543668002816
https://www.acwing.com/file_system/file/content/whole/index/content/8197923/