Каша#10308
Корови фермера Джона обожнюють сніданок з пластівців! Насправді, у них такий апетит, що кожна корова з'їдає цілу коробку пластівців за один раз.
Нещодавно на ферму надійшла партія з різних видів пластівців.
На жаль, кожного виду пластівців є лише одна коробка! Кожна з корів має улюблений і другий улюблений вид пластівців. Коли корова обирає пластівці, вона діє за наступним алгоритмом:
Якщо коробка з її улюбленими пластівцями ще є, вона бере її і йде.
Якщо ні, але коробка з її другим улюбленим видом пластівців ще є, вона бере її і йде.
Інакше вона розчаровано мукає і йде без пластівців.
Корови стоять у черзі за пластівцями. Для кожного значення i~(0 \le i \le n − 1) визначте, скільки корів зможе взяти коробку пластівців, якщо фермер Джон прибере перші корів з черги.
Перший рядок містить два цілі числа n~(1 \le n \le 10^5) і m~(1 \le m \le 10^5). Для кожного значення i~(1 \le i \le n), -ий рядок містить два цілі числа f_i і s_i~(1 \le f_i, s_i \le m і f_i \ne s_i), що позначають улюблений і другий улюблений вид пластівців -ої корови в черзі.
Для кожного значення i~(0 \le i \le n − 1) виведіть рядок, що містить відповідь для .
Якщо залишиться хоча б дві корови, то рівно двом з них дістанеться коробка пластівців.
Приклад 1