Василий приехал на посвященную криптовалютам конференцию. Для того, чтобы быть в курсе всех самых важных новостей из мира криптовалют, нужно постоянно заводить новые знакомства или пользоваться знакомствами своих друзей.
В конференции участвует $$$n$$$ человек, которые изначально не знакомы между собой. Василий может познакомить двух любых людей $$$a$$$ и $$$b$$$, которые не были знакомы до этого.
У Василия есть $$$d$$$ условий, $$$i$$$-е из которых требует, чтобы человек $$$x_i$$$ имел связь с человеком $$$y_i$$$. Формально два человека $$$x$$$ и $$$y$$$ имеют связь, если найдется цепочка $$$p_1=x, p_2, p_3, \dots, p_k=y$$$ такая, что для всех $$$i$$$ от $$$1$$$ до $$$k - 1$$$ известно, что люди под номерами $$$p_i$$$ и $$$p_{i + 1}$$$ знакомы.
Василий хочет, чтобы для каждого $$$i$$$ ($$$1 \le i \le d$$$) вы рассчитали, какое максимальное количество знакомств может иметь один человек при условии, что Василий выполнил все условия от $$$1$$$ до $$$i$$$ включительно, произведя при этом ровно $$$i$$$ знакомств. Проверка условий происходит после того, как Василий провел $$$i$$$ знакомств. Ответ для каждого $$$i$$$ необходимо найти независимо. То есть, когда вы вычисляете ответ для $$$i$$$, вы должны считать, что никто из людей еще не был знаком.
Первая строка содержит два целых числа $$$n$$$ и $$$d$$$ ($$$2 \le n \le 10^3, 1 \le d \le n - 1$$$) — количество людей и количество условий.
Следующие $$$d$$$ строк содержат по два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n, x_i \neq y_i$$$) — номера людей, которые должны иметь связь согласно $$$i$$$-му условию.
Выведите $$$d$$$ целых чисел. $$$i$$$-е число должно быть равно количеству знакомств у человека с наибольшим возможным количеством знакомств, если Василий провел $$$i$$$ знакомств и выполнил первые $$$i$$$ условий.
7 6 1 2 3 4 2 4 7 6 6 5 1 7
1 1 3 3 3 6
10 8 1 2 2 3 3 4 1 4 6 7 8 9 8 10 1 4
1 2 3 4 5 5 6 8
Пояснение для первого тестового примера:
В этом пояснении круг и вписанное число обозначают человека с соответствующим номером. Линии, соединяющие людей, обозначают то, что эти люди знакомы между собой. Человек, отмеченный красным цветом, имеет наибольшее количество знакомых. Данные способы познакомить людей не являются единственными правильными.
