F. Приближение диаметра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Джека есть граф из $$$n$$$ вершин и $$$m$$$ рёбер. Все рёбра двунаправлены и имеют единичную длину. Граф связен, то есть существует путь между любыми двумя его вершинами. Одну и ту же пару вершин может соединять несколько ребер. Граф может содержать петли, то есть рёбра, соединяющие вершину саму с собой.

Расстояние между вершинами $$$u$$$ и $$$v$$$ обозначается как $$$\rho(u, v)$$$ и равно минимально возможному количеству рёбер на пути между $$$u$$$ и $$$v$$$. Диаметр графа $$$G$$$ определяется как максимальное расстояние между парой его вершин и обозначается как $$$d(G)$$$. Формально, $$$$$$d(G) = \max_{1 \le u, v \le n}{\rho(u, v)}.$$$$$$

Джек планирует последовательно применить к своему графу $$$q$$$ модификаций. Каждая модификация добавляет ровно одно ребро. Обозначим через $$$G_i$$$ граф Джека после первых $$$i$$$ модификаций. Джек хочет вычислить $$$q + 1$$$ значений $$$d(G_0), d(G_1), d(G_2), \ldots, d(G_q)$$$.

Джек подозревает, что нахождение точных диаметров $$$q + 1$$$ графов может быть сложной задачей, поэтому ему подойдут приближённые ответы, отличающиеся от правильных ответов не более чем в два раза. Формально, Джек хочет найти последовательность целых положительных чисел $$$a_0, a_1, a_2, \ldots, a_q$$$ такую, что $$$$$$\left\lceil \frac{d(G_i)}{2} \right\rceil \le a_i \le 2 \cdot d(G_i)$$$$$$ для каждого $$$i$$$.

Взломы

Вы не можете делать взломы в этой задаче.

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

Первая строка входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$2 \leq n \leq 10^5$$$, $$$n - 1 \leq m \leq 10^5$$$, $$$0 \leq q \leq 10^5$$$) — количество вершин в данном графе, количество рёбер и количество модификаций соответственно.

Далее следуют $$$m$$$ строк, описывающие исходные рёбра графа. В $$$i$$$-й из этих строк записаны два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) — номера вершин, соединенных $$$i$$$-м ребром.

Затем следуют $$$q$$$ строк, описывающие модификации. В $$$i$$$-й из этих строк записаны два целых числа $$$u'_i$$$ и $$$v'_i$$$ ($$$1 \leq u'_i, v'_i \leq n$$$) — номера вершин, соединенных ребром, которое добавляется в граф в $$$i$$$-й модификации.

Важное примечание. Для осуществления тестирования входные данные могут содержать дополнительные строки. Они будут использоваться проверяющей программой для проверки вашего ответа на корректность. Эти строки не являются частью тестовых данных, вы не должны использовать их никоим образом, и вы можете даже не считывать их.

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

Выведите последовательность из $$$q + 1$$$ целого положительного числа $$$a_0, a_1, a_2, \ldots, a_q$$$. $$$i$$$-е из этих чисел должно отличаться от диаметра графа $$$G_i$$$ не более чем в два раза.

Примеры
Входные данные
9 10 8
1 2
2 3
2 4
3 5
4 5
5 6
5 7
6 8
7 8
8 9
3 4
6 7
2 8
1 9
1 6
4 9
3 9
7 1
Выходные данные
10 6 5 6 2 4 2 2 1
Входные данные
8 7 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 5
3 7
2 4
4 6
6 8
8 2
5 4
2 4
3 3
1 652997 124613 653029 653029 124613 124613 124613 648901 124613 653029
Выходные данные
7 5 4 4 4 3 3 3 3 3
Примечание

В первом примере последовательность значений диаметров $$$d(G_0), d(G_1), d(G_2), \ldots, d(G_q)$$$ равна $$$6, 6, 6, 3, 3, 3, 2, 2, 2$$$.

Во втором примере входные данные содержат дополнительную строку, чтение которой можно не делать. Она не являются частью теста и будет использоваться для проверки правильности вашего ответа. Вывод на второй пример содержит правильные значения $$$d(G_i)$$$.