Социальные связи

Здравствуйте. Помогите решить задачу по программированию. Программа должна быть написана на Python или C++. Срочно!



Социальные связи

В школе учатся n школьников. Каждый из них в любой момент времени дружит в социальных сетях хотя бы с половиной других учеников этой школы. Естественно, если один ученик дружит со вторым, то и второй дружит с первым. К сожалению, у школьников очень переменчивое настроение, поэтому часто какие-то пары школьников, начинают или перестают дружить. Также в школе проходят разные мероприятия в рамках которых каждой паре учеников школы необходимо периодически взаимодействовать. Но ученик может взаимодействовать только со своим другом по социальной сети. Если же они друзьями не являются, то взаимодействовать они могут только через одного или нескольких посредников.

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

В течение года у завуча появился список изменений статуса дружбы учащихся. Обработав данные, он решил каждому изменению сопоставить параметр ki. Где ki — наименьшее целое число такое, что любые два ученика могут взаимодействовать, используя не более ki посредников, после i изменений. Необходимо найти значение данного параметра для всех i от 0 до K.

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

Входные данные:
В первой строке три целых числа n, m, K (1<n≤10⁶,0<m,K≤10⁶) — количество учащихся в школе, количество друзей у каждого из них в начале учебного года, делённое на два, и количество записей по изменению статуса дружбы соответственно.

В следующих K строках находятся записи двух видов 0 x y — учащиеся с номерами x, y перестали быть друзьями в социальной сети (не гарантируется, что они до этого дружили) и 1 x y — учащиеся с номерами x, y подружились (не гарантируется, что они до этого не дружили) (1≤x,y≤n).

Выходные данные:
В K+1 строках необходимо вывести коэффициенты ki для всех i от 0 до K. Если какие то два учащихся не смогут взаимодействовать даже через посредников, то в соответствующей строке необходимо вывести число n.


Ввод
6 2 5
1 1 4
0 1 2
1 2 5
1 3 6
1 1 2

Вывод
1
1
1
1
1
0

Ограничения:
Процессорное время: 3 секунды
Память: 256 MB

1