У Джека есть граф из \(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\).
Взломы
Вы не можете делать взломы в этой задаче.
Выходные данные
Выведите последовательность из \(q + 1\) целого положительного числа \(a_0, a_1, a_2, \ldots, a_q\). \(i\)-е из этих чисел должно отличаться от диаметра графа \(G_i\) не более чем в два раза.
Примечание
В первом примере последовательность значений диаметров \(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)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|