E. Поездка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть $$$n$$$ человек изначально не знакомых друг с другом. Каждое утро двое из них, которые не были друзьями до этого, становятся друзьями.

Мы хотим запланировать поездку на каждый вечер в течение $$$m$$$ дней. Для каждой поездки нужно выбрать группу людей, которые на неё поедут. Для каждого человека должно быть верно одно из двух:

  • или этот человек не едет в поездку,
  • или хотя бы $$$k$$$ его друзей тоже едут в эту поездку.

Заметим, что дружба не является транзитивной. Если $$$a$$$ и $$$b$$$ являются друзьями, и $$$b$$$ и $$$c$$$ являются друзьями, то из этого не обязательно следует, что $$$a$$$ и $$$c$$$ являются друзьями.

Для каждого дня найдите размер максимальной группы людей, которая может поехать в поездку в этот день.

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5$$$, $$$1 \le k < n$$$) — количество людей, количество дней и минимальное количество друзей в поездке, которое требуется каждому человеку в поездке.

Строка $$$i$$$ ($$$1 \leq i \leq m$$$) из следующих $$$m$$$ строк содержит два целых числа $$$x$$$ и $$$y$$$ ($$$1\leq x, y\leq n$$$, $$$x\ne y$$$), означающие, что $$$x$$$ и $$$y$$$ становятся друзьями утром дня $$$i$$$. Гарантируется, что $$$x$$$ и $$$y$$$ не были друзьями до этого.

Выходные данные

Выведите ровно $$$m$$$ строк, где $$$i$$$-я из них ($$$1\leq i\leq m$$$) содержит размер максимальной группы людей, которая может поехать в поездку вечером дня $$$i$$$.

Примеры
Входные данные
4 4 2
2 3
1 2
1 3
1 4
Выходные данные
0
0
3
3
Входные данные
5 8 2
2 1
4 2
5 4
5 2
4 3
5 1
4 1
3 2
Выходные данные
0
0
0
3
3
4
4
5
Входные данные
5 7 2
1 5
3 2
2 5
3 4
1 2
5 3
1 3
Выходные данные
0
0
0
0
3
4
4
Примечание

В первом примере:

  • группа $$$1,2,3$$$ может поехать в поездку в дни $$$3$$$ и $$$4$$$.

Во втором примере:

  • группа $$$2,4,5$$$ может поехать в поездку в дни $$$4$$$ и $$$5$$$,
  • группа $$$1,2,4,5$$$ может поехать в поездку в дни $$$6$$$ and $$$7$$$,
  • группа $$$1,2,3,4,5$$$ может поехать в поездку в день $$$8$$$.

В третьем примере:

  • группа $$$1,2,5$$$ может поехать в поездку в день $$$5$$$,
  • группа $$$1,2,3,5$$$ может поехать в поездку в дни $$$6$$$ и $$$7$$$.