3924: 张老师的教练选择

内存限制：256 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：0 解决：0

题目描述

徐教练来到了 $NOI$ 国家队培训基地进行训练！

这次的集训召集了国内有名的 $m$ 位教练，共同来给 $n$ 名同学进行集训

而由于教练和同学的数量过多，集训基地临时决定将大班课修改为一对一上课

每位同学需要先填写自己想选择的两位教练，第 $i$ 位同学的意向教练为 $a_i,b_i$

然后训练基地会依次按照编号从小到大依次给每位同学安排教练

安排的方式是这样的：对于第 $i$ 位同学

1. 如果他的意向教练 $a_i$ 还没有被其他同学选走，则给第 $i$ 位同学配对 $a_i$ 教练
2. 如果 $a_i$ 教练在之前已经被其他同学选择，则看他的意向教练 $b_i$ 是否被其他同学选择
3. 如果他的意向教练 $b_i$ 还没有被其他同学选走，则给第 $i$ 位同学配对 $b_i$ 教练
4. 如果 $b_i$ 教练也在之前被其他同学选择，那么 $i$ 同学只能黯然离场，无法配对教练
5. 无法配对教练的同学则继续上大班课

现在徐教练打算在给每位同学配对教练时提出一个问题考考他们

对于第 $i$ 位同学，他需要回答的问题是：如果只有 $i \sim n$ 号同学，一共会有多少同学选到教练，成功开始上一对一课程？

输入

输入第一行是两个整数 $n,m$，分别表示同学数量和教练数量（教练编号为 $1 \sim m$）

接下来 $n$ 行，每行包含两个整数 $a_i,b_i$，含义如题
对于 $10\%$ 的数据，$n,m\le 5$； 

对于 $30\%$ 的数据，$n,m\le 1000$； 

对于 $100\%$ 的数据，$1 \le n,m\le 100000, 1 \le a[i],b[i] \le M, a[i] \ne b[i]$。 

输出

输出 $n$ 行，每行包含一个整数表示第 $i$ 个同学应该给出的答案

样例输入 复制 

4 2
1 2
1 2
1 2
1 2

样例输出 复制 

2
2
2
1

提示

样例解释1
对于 $1$ 号同学，他需要回答的问题是 $1 \sim 4$ 同学依次选择教练后能配对的人数
$1$ 号同学选择 $1$ 号教练
$2$ 号同学选择 $2$ 号教练
$3,4$ 号同学的意向教练都被选走，无法配对，所以答案为 $2$

对于 $2$ 号同学，他需要回答的问题是 $2 \sim 4$ 同学依次选择教练后能配对的人数
$2$ 号同学选择 $1$ 号教练
$3$ 号同学选择 $2$ 号教练
$4$ 号同学的意向教练都被选走，无法配对，所以答案为 $2$

对于 $3$ 号同学，他需要回答的问题是 $3 \sim 4$ 同学依次选择教练后能配对的人数
$3$ 号同学选择 $1$ 号教练
$4$ 号同学选择 $2$ 号教练
答案为 $2$

对于 $4$ 号同学，他需要回答的问题是 $4 \sim 4$ 同学依次选择教练后能配对的人数
$4$ 号同学选择 $1$ 号教练
答案为 $1$

来源/分类

提交提交记录统计露一手!