Задача: Зерновые

Коровы Фермера Джона очень любят хлопья на завтрак. И едят по ящику хлопьев за раз.
Ферма недавно получила M (1≤M≤10⁵) различных типов хлопьев. К несчастью, хлопьев каждого вида есть ровно один ящик. Каждая из N коров (1≤N≤10⁵) имеет любимый вид хлопьев и второй любимый вид хлопьев. Процесс выбора хлопьев коровами происходит так:

1. Если ящик с её любимыми хлопьями ещё доступен, корова берёт его и уходит.
2. Иначе, если ящик с её вторыми любимыми хлопьями ещё доступен, корова берёт его и уходит.
3. Иначе она уходит с пустыми копытами

Коровы выстроились в очередь для получения хлопьев. Для каждой из 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

           

Ваш ответ: