Aimai Trip
暂无测试数据。
有 $n$ 只猫猫在玩捉迷藏。猫猫们的编号分别为 $1,2,\cdots,n$。
屋子里有 $k$ 个房间，每个房间只能容纳一只猫猫。
每个房间有一定的属性，可以用 $x_i,y_i$ 来表示，意为：
- 这个房间要么空着，要么容纳第 $x_i$ 只猫猫，要么容纳第 $y_i$ 只猫猫。
现在云浅可以买下前 $m$ 个房间给猫猫们使用。云浅想要知道，$m$ 的值至少是多少，才能容纳所有猫猫。保证买下所有房间后一定可以容纳所有猫猫。
为了更好地帮助小可爱，你还需要输出一个方案。如果有多个可行的方案，输出任意一个即可。
输入格式
第一行两个正整数 $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$ 只猫猫。
数据范围
对于 $100\%$ 的数据，$1\le n \le 10^5,1\le k\le 2\times 10^5,1\le x_i,y_i\le n,x_i\neq y_i$。
| 测试点编号 | $n$ | $k$ |
|---|---|---|
| $1\sim 6$ | $\le 20$ | $\le 20$ |
| $7\sim 10$ | $\le 1000$ | $\le 1000$ |
| $11\sim 14$ | $\le 1000$ | $\le 10^5$ |
| $15\sim 20$ | $\le 10^5$ | $\le 2\times 10^5$ |
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
3 6
1 2 3 3 2 1
3 2 1 1 2 3
3
1 1 1