给定长度为
对于
定义极大匹配方案
- 对于任意
, 且 构成匹配; - 每一个整数
在 中出现至多一次; - 在满足以上条件的前提下,满足
的二元组 数量最多,即 最大; - 在满足以上条件的前提下,
最大。
给定
你需要对于每个
输入格式
从标准输入读入数据。
输入的第一行两个整数
第二行
第三行
接下来
输出格式
输出到标准输出。
输出
样例 #1
样例输入 #1
5 5 1 2 1 1 2 0 0 0 0 0 2 2 1 4 2 0 4 2 1 2 2 0 1 1 1
样例输出 #1
0 1 1 2 1 1
样例 1 解释
- 初始情况,由于所有的
都等于 ,因此没有二元组构成匹配,极大匹配方案的大小为 ,故第一行输出 。 - 进行第一次修改后,
,极大匹配方案为 ,故第二行输出 。 - 进行前三次修改后,序列
为 ,序列 为 。极大匹配方案为 ,故第四行输出 。注意此时 有 , ,并不构成匹配。
样例 #2
样例输入 #2
10 10 2 1 2 2 2 2 1 2 2 2 1 1 0 0 0 0 1 0 0 0 3 2 0 5 1 0 9 1 1 4 2 1 8 1 1 2 1 0 1 2 1 8 2 0 1 1 1 9 1 0
样例输出 #2
1 1 1 2 3 3 4 4 3 3 2
子任务
对于所有测试数据,
, ;- 对于
, , ; - 每次修改中有
, , 。
- Subtask 1(
): , 。 - Subtask 2(
): , 。 - Subtask 3(
): 。 - Subtask 4(
): 。 - Subtask 5(
): 。 - Subtask 6(
):无特殊限制。