Description
小恩对邻国老是搞军演十分不满，于是决定发射 LD 导弹表示抗议。
小恩的计划是这样的，他有 (n) 个导弹发射基地，基地与基地之间会有无向的连边（无重边、无自环）。小恩可以进行合并操作。合并是指把两个没有连边的两个基地合为一个基地，如果之前某基地与执行合并操作的某一基地（或两个）有连边，则该基地与合并后的基地有连边，这样，每次执行此操作总基地数就会减一。
现在小恩希望用最少的合并操作把所有基地传承一条链，问最少的操作数是多少。
Input
第一行两个整数 (n, m) ，表示基地数，边数。
接下来 (m) 行，每行两个整数，表示从 (x) 到 (y) 有一条连边。
Sample
Sample Input
4 2
1 2
3 4
Sample Output
1
Sample Input
3 3
1 2
2 3
1 3
Sample Output
-1
Limit
对于 (30\%) 的数据， (n le 10,m le 100) 。
对于 (100\%) 的数据， (nle 1000,mle 100000)
Solution
谴责这两天的出题人，数据出锅、题面意思不清 、还有阴险的针织隐喻 。
被 xtc 大爷教育了一番，发现是一道傻逼乱搞题。
显然是连通块内部先怎么搞一下成一条链，再把这些链首尾相接。所以先用个并查集什么的把块处理出来，再在内部搞。
显然我们随手画个图就知道，如果一个图内有奇环，那么它就肯定无法通过某种操作合并成链，反之一定可以。
那么此时我们就有了一种很高明的做法。先枚举根，然后从根对这个图进行分层。合并就把同一层的点合并到一起。无法合并的情况就是无论根在哪一个点，都存在同一层点之间的连边，因为这样就形成了奇环。
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define N 1001
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define INF 2000000000
inline int read() {
int x = 0, flag = 1; char ch = getchar(); while (!isdigit(ch)) { if (!(ch ^ '-')) flag = -1; ch = getchar(); }
while (isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); return x * flag;
}
int n, m, fa[N], dep[N], q[N], bar[N], ans = -1;
vector<int> block[N];
struct edge { int v, next; }e[1000001];
int head[N], tot = 1;
inline void add(int u, int v) { e[++tot].v = v, e[tot].next = head[u], head[u] = tot; }
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
bool bfs(int x) {
int l = 1, r = 1; q[1] = x;
while (l <= r) {
int u = q[l++]; bar[dep[u]]++;
for (int i = head[u], v; i; i = e[i].next) {
if (dep[v = e[i].v] == dep[u]) return 0;
if (!dep[v]) dep[v] = dep[u] + 1, q[++r] = v;
}
}
return 1;
}
int main() {
n = read(), m = read();
rep(i, 1, n) fa[i] = i;
rep(i, 1, m) {
int u = read(), v = read(); add(u, v), add(v, u);
u = find(u), v = find(v); if (u ^ v) fa[u] = v;
}
rep(i, 1, n) find(i), block[fa[i]].push_back(i);
rep(i, 1, n) if (!block[i].empty()) ans++;
rep(k, 1, n) if (block[k].size() > 1) {
int ret = INF;
for (int i = 0; i < block[k].size(); i++) {
for (int j = 0; j < block[k].size(); j++) dep[block[k][j]] = 0, bar[j + 1] = 0;
dep[block[k][i]] = 1;
if (bfs(block[k][i])) {
int cnt = 0; for (int j = 1; j < block[k].size() + 1; j++) if (bar[j]) cnt += bar[j] - 1;
ret = min(ret, cnt);
}
}
if (ret == INF) puts("-1"), exit(0);
ans += ret;
}
printf("%d", ans);
return 0;
}