Вам дано дерево с \(n\) вершинами, пронумерованными \(1, 2, \ldots, n\). Изначально все вершины окрашены в белый цвет.
Вы можете выполнить следующую двухэтапную операцию:
- Выбрать вершину \(v\) (\(1 \leq v \leq n\)) и расстояние \(d\) (\(0 \leq d \leq n-1\)).
- Для всех вершин \(u\) (\(1 \leq u \leq n\)) таких, что \(\text{dist}^\dagger(u,v)=d\), покрасить \(u\) в черный цвет.
Постройте последовательность операций для перекрашивания всех вершин дерева в черный цвет, используя минимально возможное количество операций. Можно показать, что это всегда можно сделать, используя не более \(n\) операций.
\(^\dagger\) \(\text{dist}(x, y)\) обозначает количество ребер на (единственном) простом пути между вершинами \(x\) и \(y\) на дереве.
Выходные данные
Для каждого набора входных данных сначала выведите одно целое число \(op\) \((1 \le op \le n)\) — минимальное количество операций, необходимых для перекрашивания всех вершин дерева в черный цвет.
Затем выведите \(op\) строк, каждая из которых содержит \(2\) целых числа. В \(i\)-й строке должны содержаться значения \(v\) и \(d\), выбранные для \(i\)-й операции (\(1 \le v \le n\), \(0 \le d \le n - 1\)).
Необходимо, чтобы в результате \(op\) операций все вершины были покрашены в черный цвет.
Если существует несколько решений, вы можете вывести любое из них.
Примечание
В первом наборе входных данных существует только одна возможная операция, и ее выполнение дает правильный ответ.
Во втором наборе входных данных первая операция перекрашивает вершину \(2\) в черный цвет, а вторая операция перекрашивает вершину \(1\) в черный цвет. Можно показать, что за одну операцию невозможно перекрасить обе вершины в черный цвет, поэтому минимальное количество необходимых операций равно \(2\). Другим возможным решением является использование \(2\) операций: \((u, r) = (1, 0)\) и \((u, r) = (2, 0)\).
В третьем наборе входных данных первая операция перекрашивает вершины \(2\), \(3\) и \(4\) в черный цвет, а вторая операция перекрашивает вершину \(1\) в черный цвет. Опять же, можно показать, что за \(1\) операцию невозможно перекрасить все вершины в черный цвет, поэтому минимальное количество необходимых операций равно \(2\).
В четвертом наборе входных данных первая операция перекрашивает вершины \(4\), \(1\) и \(7\) в черный цвет, вторая операция перекрашивает вершины \(2\), \(5\) и \(6\) в черный цвет, а третья операция перекрашивает вершины \(3\) и \(7\) в черный цвет. Обратите внимание, что вершину \(7\) разрешено перекрашивать в черный цвет дважды.
Таким образом, каждая вершина была перекрашена хотя бы один раз, причем вершина \(7\) была перекрашена дважды. Можно показать, что невозможно перекрасить все вершины в черный цвет менее чем за \(3\) хода.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
2
1 2
4
1 2
1 3
1 4
7
2 7
3 2
6 4
5 7
1 6
6 7
|
1
1 0
2
1 1
2 1
2
1 1
2 1
3
6 1
7 1
2 1
|