Дороги не роскошь, а место передвижения

문제

Страна N состоит из $nn$ городов, пронумерованных от $11$ до $nn$, однако в ней совсем нет дорог! Президентом страны было принято решение построить $mm$ дорог в течение $mm$ дней, при этом каждый день будет строиться ровно одна новая дорога. Дополнительно, в целях поддержки миграции населения было принято решение сделать все дороги односторонними, и планировать дорожную сеть таким образом, что если существует путь из города $ii$ в город $jj$, то пути из города $jj$ в город $ii$ не существует.

Для популяризации новых дорог среди населения страны N было решено ежедневно проводить серию автопробегов по городам страны. Каждая машина автопробега стартует в некотором городе, после чего совершает перемещения по уже построенным к данному дню дорогам и заканчивает свой маршрут также в каком-нибудь городе. При этом разрешается, чтобы город старта совпадал с городом финиша, то есть чтобы машина не совершала ни одного переезда по дорогам. Преследуя одновременно цели порадовать жителей страны и цели экономии топлива водителей, организаторы решили каждый день выбирать набор маршрутов согласно следующим правилам:

1. Каждый город должен быть посещён машиной автопробега. Посещёнными считаются начальный, конечный и все промежуточные города на пути любой из машин.
2. Никакой город не должен быть посещён машинами автопробега более одного раза.
3. Общее количество используемых машин должно быть минимальным.

Министерство транспорта страны N уже запланировало постройку ровно одной дороги для каждого из ближайших $mm$ дней. Теперь представители министерства просят вас для каждого из дней определить, какое минимальное количество машин потребуется для автопробега. Считайте, что в день $ii$ доступны дороги, построенные в дни $1,2,\dots ,i1,\; 2,\; \backslash ldots,\; i$.

입력

В первой строке входных данных записаны два числа $nn$ и $mm$ ($2\le n\le 10002\; \backslash leq\; n\; \backslash leq\; 1000$, $1\le m\le 1000001\; \backslash leq\; m\; \backslash leq\; 100\backslash ,000$) --- количество городов в стране N и количество дней, в течение которых будут строиться дороги.

В каждой из последующих $mm$ строк записаны два целых числа $u_{i}u\_i$ и $v_{i}v\_i$ ($1\le u_i,v_i\le n1\; \backslash leq\; u\_i,\; v\_i\; \backslash leq\; n$, $u_i\mathrm{\ne }{v}_{i}u\_i\; \backslash ne\; v\_i$), означающих что в $ii$-й день будет построена односторонняя дорога из города $u_{i}u\_i$ в город $v_{i}v\_i$. Допускается, что будет построена дорога между двумя городами, уже соединёнными дорогой ранее. Гарантируется, что после постройки любой дороги, если существует путь из города $aa$ в город $bb$, то не существует пути из города $bb$ в город $aa$.

출력

Выведите $mm$ чисел, $ii$-е из которых равняется минимальному количеству машин для автопробега после постройки первых $ii$ дорог.

힌트

В первом примере после после постройки первых двух дорог всё равно потребуется запустить как минимум две машины. Например, одна из них может проехать из города $11$ в город $22$, а другая начнёт в городе $33$ и закончит автопробег в нём же. После постройки всех дорог достаточно одной машины, которая поедет по маршруту $1\to 2\to 31\; \backslash rightarrow\; 2\; \backslash rightarrow\; 3$.

Во втором примере, после постройки всех дорог можно было бы посетить все города используя только два автомобиля, но этому мешает условие, что никакой город не должен быть посещён больше, чем одним автомобилем пробега.