Коровы Фермера Джона очень любят хлопья на завтрак. И едят по ящику хлопьев за раз.
Ферма недавно получила M (1≤M≤10
5) различных типов хлопьев. К несчастью, хлопьев каждого вида есть ровно один ящик. Каждая из N коров (1≤N≤10
5) имеет любимый вид хлопьев и второй любимый вид хлопьев. Процесс выбора хлопьев коровами происходит так:
- Если ящик с её любимыми хлопьями ещё доступен, корова берёт его и уходит.
- Иначе, если ящик с её вторыми любимыми хлопьями ещё доступен, корова берёт его и уходит.
- Иначе она уходит с пустыми копытами
Коровы выстроились в очередь для получения хлопьев. Для каждой из 0≤i≤N−1, коров определите, сколько коров возьмут ящик с хлопьями, если ФД удалит из очереди первые i коров.
Входные данные
Первая строка содержит два разделённых пробелом целых числа N и M.
Для каждой 1 ≤ i ≤ N, i-ая строка содержит два разделённых пробелом целых числа f
i и s
i (1 ≤ f
i,s
i ≤ M и f
i ≠ s
i), обозначающих любимый и второй любимый вид хлопьев i-ой коровы в очереди.
Выходные данные
Для каждой 0 ≤ i≤ N−1, выведите строку, содержащую ответ для i.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 2
1 2
1 2
1 2
1 2 |
2
2
2
1 |