Вам дан простой неориентированный граф, состоящий из \(n\) вершин. Граф не содержит петель, между каждой парой вершин существует не более одного ребра. Ваша задача проста: сделать граф связным.
Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):
- Выберите произвольную вершину \(u\).
- Для каждой вершины \(v\), для которой \(v\ne u\), если \(v\) смежна с \(u\), удалите ребро между \(u\) и \(v\), иначе добавьте ребро между \(u\) и \(v\).
Найдите минимальное количество операций, необходимых для того, чтобы сделать граф связным. Также найдите любую последовательность операций минимальной длины, которая делает граф связным.
Выходные данные
Для каждого набора входных данных в первой строке выведите целое число \(m\) — минимально необходимое количество операций.
Если \(m\) больше нуля, то выведите дополнительную строку, состоящую из \(m\) целых чисел — вершин, выбранных в операциях в вашем решении. Если существует несколько решений с минимальным количеством операций, выведите любое из них.
Примечание
В первом наборе входных данных граф связен в начале, поэтому ответ — \(0\).
Во втором наборе входных данных, если мы выполним операцию с вершиной \(1\), то получим следующий граф, представленный следующей матрицей смежности:
\(\) \begin{bmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{bmatrix} \(\)
Очевидно, что приведенный выше граф является связным.
В третьем наборе входных данных, если мы проделаем операцию с вершинами \(3\) и \(4\), то получим следующий граф, представленный следующей матрицей смежности:
\(\) \begin{bmatrix} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0 \end{bmatrix} \(\)
Очевидно, что приведенный выше граф является связным, и можно доказать, что мы не можем выполнить менее \(2\) операций, чтобы сделать граф связным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
011
100
100
3
000
001
010
4
0100
1000
0001
0010
6
001100
000011
100100
101000
010001
010010
|
0
1
1
2
3 4
3
2 5 6
|