Есть \(n\) человек изначально не знакомых друг с другом. Каждое утро двое из них, которые не были друзьями до этого, становятся друзьями.
Мы хотим запланировать поездку на каждый вечер в течение \(m\) дней. Для каждой поездки нужно выбрать группу людей, которые на неё поедут. Для каждого человека должно быть верно одно из двух:
- или этот человек не едет в поездку,
- или хотя бы \(k\) его друзей тоже едут в эту поездку.
Заметим, что дружба не является транзитивной. Если \(a\) и \(b\) являются друзьями, и \(b\) и \(c\) являются друзьями, то из этого не обязательно следует, что \(a\) и \(c\) являются друзьями.
Для каждого дня найдите размер максимальной группы людей, которая может поехать в поездку в этот день.
Выходные данные
Выведите ровно \(m\) строк, где \(i\)-я из них (\(1\leq i\leq m\)) содержит размер максимальной группы людей, которая может поехать в поездку вечером дня \(i\).
Примечание
В первом примере:
- группа \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4 2
2 3
1 2
1 3
1 4
|
0
0
3
3
|
|
2
|
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
|
|
3
|
5 7 2
1 5
3 2
2 5
3 4
1 2
5 3
1 3
|
0
0
0
0
3
4
4
|