封锁阳光大学

Problem Statement

曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。

阳光大学的校园是一张由 $n$ 个点构成的无向图，$n$ 个点之间由 $m$ 条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。

询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。

Input

第一行两个正整数，表示节点数和边数。接下来 $m$ 行，每行两个整数 $u,v$，表示点 $u$ 到点 $v$ 之间有道路相连。

Output

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

Sample Input #1

Sample Output #2

1

Impossible

Sample Input #1

Sample Output #2

1

1

Constraints

对于 $100%$ 的数据，$1\le n \le 10^4$，$1\le m \le 10^5$，保证没有重边。

Solving

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62


const int N = 1e4 + 100;
const int M = 1e5 + 100;
int n, m;
struct node {
    int to, next;
} edge[M << 1];
int cnt = 0;
int head[N];
void add(int u, int v) {
    cnt++;
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
int color[N];  // 0 表示未染色，1 和 2 表示两种不同的颜色
int cnt1, cnt2;  // 分别记录两种颜色的节点数量
bool dfs(int u,int c) 
{
    color[u] = c;
    if (c == 1) cnt1++;
    else cnt2++;
    for (int i = head[u]; i; i = edge[i].next) 
	{
        int v = edge[i].to;
        if (color[v] == 0) 
		{
			//如果相连的下一个顶点未涂色但涂不了与当前相反的颜色 
            if(!dfs(v,3-c)) 
			return false;
        } 
		else if (color[v]==c) 
		{		
            return false;//相邻节点颜色相同，存在奇数环
        }
    }
    return true;
}
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) 
	{
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) 
	{
        if(color[i] == 0) 
		{
            cnt1 = 0,cnt2 = 0;
            if (!dfs(i,1)) 
			{
                cout << "Impossible" << endl;
                return;
            }
            ans += min(cnt1,cnt2);
        }
    }
    cout << ans << endl;
}