|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
// TODO 只过了两个测试点，因为没有测试数据，所以不知道为什么，两个样例都是可以过的
|
|
|
|
|
|
// 2023-03-20
|
|
|
|
|
|
// 对拍也不知道怎么做，一会问一下ChatGpt
|
|
|
|
|
|
|
|
|
|
|
|
// 明天研究一下对拍：https://www.cnblogs.com/EdisonBa/p/13509379.html
|
|
|
|
|
|
|
|
|
|
|
|
const int N = 2e5 + 10, M = N << 1;
|
|
|
|
|
|
|
|
|
|
|
|
int n, k; // 猫猫数量，房间总数
|
|
|
|
|
|
int x[N], y[N]; // i:第几个房间,x[i]:可以住哪只猫猫,y[i]:可以住哪只猫猫
|
|
|
|
|
|
|
|
|
|
|
|
// 链式前向星
|
|
|
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
|
|
|
void add(int a, int b, int c = 0) {
|
|
|
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int st[M]; // 房间是不是使用过
|
|
|
|
|
|
int flag; // 所有猫猫是不是都有了房间
|
|
|
|
|
|
int out;
|
|
|
|
|
|
vector<int> path;
|
|
|
|
|
|
// 树+dfs搜索
|
|
|
|
|
|
void dfs(int u, int m) {
|
|
|
|
|
|
if (u == n + 1) {
|
|
|
|
|
|
flag = 1;
|
|
|
|
|
|
if (!out) {
|
|
|
|
|
|
// 记录最新获得的结果
|
|
|
|
|
|
path.clear();
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = 1; i <= m; i++) {
|
|
|
|
|
|
if (st[i] == x[i])
|
|
|
|
|
|
path.push_back(1);
|
|
|
|
|
|
else
|
|
|
|
|
|
path.push_back(2);
|
|
|
|
|
|
}
|
|
|
|
|
|
out = 1;
|
|
|
|
|
|
}
|
|
|
|
|
|
return;
|
|
|
|
|
|
}
|
|
|
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
|
|
|
int room = w[i]; // 哪个房间
|
|
|
|
|
|
if (st[room]) continue; // 如果这个房间用人用了，就不能用
|
|
|
|
|
|
// 记录
|
|
|
|
|
|
st[room] = u; // 记录这个房间谁在用
|
|
|
|
|
|
// 递归
|
|
|
|
|
|
dfs(u + 1, m);
|
|
|
|
|
|
// 回溯
|
|
|
|
|
|
st[room] = 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
bool chk(int m) {
|
|
|
|
|
|
// 清空
|
|
|
|
|
|
memset(h, -1, sizeof h);
|
|
|
|
|
|
idx = 0;
|
|
|
|
|
|
flag = 0;
|
|
|
|
|
|
out = 0;
|
|
|
|
|
|
memset(st, 0, sizeof st);
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = 1; i <= m; i++) { // 前m个房间
|
|
|
|
|
|
add(x[i], y[i], i); // 将房间号作为边权，理解为x[i]号小猫，可以用掉这个与它相连的房间，y[i]号小猫也可以用掉这个与它相边的房间
|
|
|
|
|
|
add(y[i], x[i], i);
|
|
|
|
|
|
}
|
|
|
|
|
|
// 检查一下现在可以满足每个小猫都有房间住吗？
|
|
|
|
|
|
dfs(1, m);
|
|
|
|
|
|
|
|
|
|
|
|
return flag;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
freopen("cats.in", "r", stdin);
|
|
|
|
|
|
// freopen("cats.out", "w", stdout);
|
|
|
|
|
|
|
|
|
|
|
|
memset(h, -1, sizeof h);
|
|
|
|
|
|
cin >> n >> k;
|
|
|
|
|
|
for (int i = 1; i <= k; i++) cin >> x[i];
|
|
|
|
|
|
for (int i = 1; i <= k; i++) cin >> 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;
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = 0; i < path.size(); i++)
|
|
|
|
|
|
cout << path[i] << " ";
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
