Каша

Корови фермера Джона обожнюють сніданок з пластівців! Насправді, у них такий апетит, що кожна корова з'їдає цілу коробку пластівців за один раз.

Нещодавно на ферму надійшла партія з $m$ різних видів пластівців.

На жаль, кожного виду пластівців є лише одна коробка! Кожна з $n$ корів має улюблений і другий улюблений вид пластівців. Коли корова обирає пластівці, вона діє за наступним алгоритмом:

• Якщо коробка з її улюбленими пластівцями ще є, вона бере її і йде.

• Якщо ні, але коробка з її другим улюбленим видом пластівців ще є, вона бере її і йде.

• Інакше вона розчаровано мукає і йде без пластівців.

Корови стоять у черзі за пластівцями. Для кожного значення $i(0\le i\le n-1)$ визначте, скільки корів зможе взяти коробку пластівців, якщо фермер Джон прибере перші $i$ корів з черги.

Вхідні дані

Перший рядок містить два цілі числа $n(1\le n\le 10^5)$ і $m(1\le m\le 10^5)$. Для кожного значення $i(1\le i\le n)$, $i$-ий рядок містить два цілі числа $f_i$ і $s_i(1\le f_i,s_i\le m$ і $f_i\ne s_i)$, що позначають улюблений і другий улюблений вид пластівців $i$-ої корови в черзі.

Вихідні дані

Для кожного значення $i(0\le i\le n-1)$ виведіть рядок, що містить відповідь для $i$.

Приклади

Якщо залишиться хоча б дві корови, то рівно двом з них дістанеться коробка пластівців.