|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 2e5 + 10;
|
|
|
int n, k;
|
|
|
int x[N], y[N];
|
|
|
|
|
|
struct Node {
|
|
|
int to, id; // id:哪个房间，to:另一只猫猫的号码
|
|
|
};
|
|
|
|
|
|
vector<Node> g[N];
|
|
|
vector<int> S;
|
|
|
bool st[N];
|
|
|
|
|
|
// void getnodes(int u) {
|
|
|
// st[u] = 1;
|
|
|
// S.push_back(u);
|
|
|
// for (auto e : g[u]) {
|
|
|
// int v = e.to;
|
|
|
// if (!st[v]) getnodes(v);
|
|
|
// }
|
|
|
// }
|
|
|
|
|
|
vector<int> C;
|
|
|
int fa[N], pre[N], res[N];
|
|
|
bool fi;
|
|
|
|
|
|
void findcycle(int u) {
|
|
|
st[u] = 1; // u号小猫已经找过房间了
|
|
|
for (auto e : g[u]) { // 遍历u号小猫的每个可用房间
|
|
|
int v = e.to, i = e.id;
|
|
|
if (i == pre[u]) continue; // 不走回头路
|
|
|
|
|
|
if (!st[v]) { // 进入搜索
|
|
|
fa[v] = u, pre[v] = i, findcycle(v);
|
|
|
continue;
|
|
|
}
|
|
|
|
|
|
if (fi) continue;
|
|
|
int q = u;
|
|
|
while (q != v) {
|
|
|
C.push_back(q), res[pre[q]] = (x[pre[q]] == q ? 2 : 1);
|
|
|
q = fa[q];
|
|
|
}
|
|
|
res[i] = (x[i] == u ? 1 : 2);
|
|
|
fi = 1;
|
|
|
C.push_back(v);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
bool chk(int m) {
|
|
|
// 多次二分，清空现场
|
|
|
for (int i = 1; i <= n; i++) g[i].clear();
|
|
|
memset(st, 0, sizeof(st)), memset(pre, 0, sizeof(pre)), memset(fa, 0, sizeof(fa));
|
|
|
|
|
|
// 前m个房间
|
|
|
for (int i = 1; i <= m; i++) {
|
|
|
int u = x[i], v = y[i];
|
|
|
// 无向图建图
|
|
|
g[u].push_back({v, i}); // u这只猫猫，可以使用i这个房间，另外一个可以使用i房间的猫猫是v号
|
|
|
g[v].push_back({u, i}); // v这只猫猫，可以使用i这个房间，另外一个可以使用i房间的猫猫是u号
|
|
|
}
|
|
|
|
|
|
for (int i = 1; i <= n; i++) { // 每只猫
|
|
|
if (st[i]) continue; // 如果访问过，就下一个
|
|
|
fi = 0, C.clear(); // fi：i号小猫在哪个房间里？
|
|
|
findcycle(i); // 为i号小猫找房间
|
|
|
if (!fi) return 0; // 如果没有找到合适的房间，那么就表示当前的m太小的，需要扩大
|
|
|
}
|
|
|
return 1; // 检查通过，返回OK
|
|
|
}
|
|
|
|
|
|
void dfs(int u) {
|
|
|
st[u] = 1;
|
|
|
for (auto e : g[u]) {
|
|
|
int v = e.to, i = e.id;
|
|
|
if (st[v] || res[i] != 0) continue;
|
|
|
res[i] = (x[i] == v ? 1 : 2);
|
|
|
dfs(v);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// void getans(int m) {
|
|
|
// for (int i = 1; i <= n; i++) g[i].clear();
|
|
|
// memset(st, 0, sizeof(st)), memset(pre, 0, sizeof(pre));
|
|
|
// memset(fa, 0, sizeof(fa)), memset(res, 0, sizeof(res));
|
|
|
|
|
|
// for (int i = 1; i <= m; i++) {
|
|
|
// int u = x[i], v = y[i];
|
|
|
// g[u].push_back({v, i}), g[v].push_back({u, i});
|
|
|
// }
|
|
|
|
|
|
// for (int i = 1; i <= n; i++) {
|
|
|
// if (st[i]) continue;
|
|
|
// S.clear();
|
|
|
// getnodes(i);
|
|
|
// fi = 0;
|
|
|
// for (int p : S) st[p] = 0;
|
|
|
// C.clear();
|
|
|
// findcycle(i);
|
|
|
// for (int p : S) st[p] = 0;
|
|
|
// for (int p : C) st[p] = 1;
|
|
|
// for (int p : C) dfs(p);
|
|
|
// for (int p : S) st[p] = 1;
|
|
|
// }
|
|
|
|
|
|
// for (int i = 1; i <= m; i++) cout << res[i] << " ";
|
|
|
// puts("");
|
|
|
// }
|
|
|
|
|
|
int main() {
|
|
|
freopen("cats.in", "r", stdin);
|
|
|
// freopen("cats.out", "w", stdout);
|
|
|
|
|
|
cin >> n >> k; // n只小猫，k个房间
|
|
|
for (int i = 1; i <= k; i++) cin >> x[i]; // k个房间，可以容纳x[i]的猫猫
|
|
|
for (int i = 1; i <= k; i++) cin >> y[i]; // k个房间，可以容纳y[i]的猫猫
|
|
|
|
|
|
int L = 1, R = k, ans = L; // 二分答案
|
|
|
while (L <= R) {
|
|
|
int mid = (L + R) >> 1;
|
|
|
if (chk(mid)) // 如果每个猫猫都可以有房间，那么检查通过,说明房间的数量还是很宽松的
|
|
|
R = mid - 1, ans = mid;
|
|
|
else
|
|
|
L = mid + 1;
|
|
|
}
|
|
|
|
|
|
// 输出数量
|
|
|
cout << ans << endl;
|
|
|
|
|
|
// 输出方案
|
|
|
// getans(ans);
|
|
|
|
|
|
return 0;
|
|
|
} |
