Есть \(n\) человек изначально не знакомых друг с другом. Каждое утро двое из них, которые не были друзьями до этого, становятся друзьями.
Мы хотим запланировать поездку на каждый вечер в течение \(m\) дней. Для каждой поездки нужно выбрать группу людей, которые на неё поедут. Для каждого человека должно быть верно одно из двух:
Заметим, что дружба не является транзитивной. Если \(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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач