3902. [桐柏邀请赛S14]trip

【题目描述】

有 $n$ 只猫猫在玩捉迷藏。猫猫们的编号分别为 $1,2,\cdots,n$。

屋子里有 $k$ 个房间，每个房间只能容纳一只猫猫。

每个房间有一定的属性，可以用 $x_i,y_i$ 来表示，意为：

- 这个房间要么空着，要么容纳第 $x_i$ 只猫猫，要么容纳第 $y_i$ 只猫猫。

现在云浅可以买下前 $x$ 个房间给猫猫们使用。云浅想要知道，$x$ 的值至少是多少，才能容纳所有猫猫。保证买下所有房间后一定可以容纳所有猫猫。

为了更好地帮助猫猫，你还需要输出一个方案。如果有多个可行的方案，输出任意一个即可。

【输入格式】

第一行两个正整数 $n,k$。

第二行 $k$ 个正整数 $x_1,\cdots,x_k$，表示每个房间的第一种属性。

第三行 $k$ 个正整数 $y_1,\cdots,y_k$，表示每个房间的第二种属性。

【输出格式】

先输出一行一个正整数 $m$ 表示答案。

第二行输出 $m$ 个正整数，其中，若第 $i$ 个数为 $0$ 则表示第 $i$ 个房间空着不用，第 $i$ 个数为 $1$ 则表示分给第 $x_i$ 只猫猫，第 $i$ 个数为 $2$ 则表示分给第 $y_i$ 只猫猫。

【样例输入】

7 10
1 2 6 3 1 4 6 7 3 1
2 1 7 4 5 2 5 5 2 3

【样例输出】

7
2 2 2 1 2 1 1

【样例说明】

显然前六个房间无法容纳所有猫猫。按照输出的方案，每只猫猫都恰好被分到了一个房间里，每个房间里也都恰好有一只猫猫。

【数据规模与约定】

对于 $100\%$ 的数据，$1\le n\le 2\times 10^5,1\le k\le 5\times 10^5,1\le x_i,y_i\le n,x_i\neq y_i$。

【来源】

桐柏邀请赛S14 Task4