该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

附加文件

题目描述

有一个长为 $n$ 的序列 $a$，初始 $a_i$ 都是 $0$，以及一个操作序列 $(x_1,y_1),\cdots,(x_c,y_c)$，具体地，一个操作 $(x,y)$ 代表把 $a_x$ 修改为 $y$。保证 $1\le x_i\le n,1\le y_i\le m$，这里 $m$ 是给定的常数。

定义一个操作序列合法，当且仅当经过这个操作序列之后，$a$ 满足：

• 所有 $a_i$ 均不为 $0$。
• 序列 $a$ 中的不同元素个数需要 $\ge k$，其中 $k$ 是给定的正整数。

现在你可以从你的操作序列 $(x_1,y_1),\cdots,(x_c,y_c)$ 中忽略若干个操作，然后把剩下的操作分成尽可能多的子序列，使得每个子序列都是合法的操作序列。请你求出最多能分出多少个子序列，并构造一种方案。

具体地，你需要输出 $c$ 个正整数 $\text{id}_1,\cdots,\text{id}_c$ 表示每个操作被分到了哪个子序列中，还是删除了。如果 $\text{id}_i=0$，代表你忽略了这次操作，否则代表你把这次操作分到了第 $i$ 个子序列内。你需要保证每个分出的子操作序列都是合法的。

输入格式

第一行四个正整数 $n,m,c,k$。

接下来 $c$ 行，每行两个正整数 $x,y$ 表示操作序列中的一个操作。

输出格式

第一行输出一个正整数 $d$ 表示最多能分出多少个子序列。

接下来一行 $c$ 个正整数 $\text{id}_1,\cdots,\text{id}_c$ 表示每个操作被分到了哪个子序列中，还是删除了。具体地，你需要保证 $0\le \text{id}_i\le d$，如果 $\text{id}_i=0$，代表你忽略了这次操作，否则代表你把这次操作分到了第 $i$ 个子序列内。你需要保证每个分出的子操作序列都是合法的。

如有非唯一解，输出任意一种均可。

样例 $1$ 输入

3 3 10 2
3 1
3 3
3 2
2 3
2 2
2 2
3 3
2 1
1 3
1 3

样例 $1$ 输出

2
0 0 2 0 1 2 1 0 1 2

样例 $1$ 解释

第一个分出来的操作序列是 $(2,2),(3,3),(1,3)$，第二个则是 $(3,2),(2,2),(1,3)$，都是合法的

样例 $2$ 输入

3 4 5 1
1 1
1 1
1 1
1 1
1 1

样例 $2$ 输出

0
0 0 0 0 0

样例 $3 \sim 9$

见下发文件，这些样例依次满足子任务 $1,2,3,4,5,6,7$ 的约束。

测试点约束

对于所有数据，$1\le n,m\le 1000,1\le c\le 5000,1\le k\le \min(n,m)$。