Вам дано дерево из \(n\) вершин, пронумерованных от \(1\) до \(n\). Деревом называется связный неориентированный граф без циклов.
Для всех \(i=1,2, \ldots, n\) обозначим за \(w_i\) вес \(i\)-й вершины. Вершина называется хорошей, если ее вес равен сумме весов всех ее соседей.
Изначально веса в вершинах не определены. Выберете для каждой вершины положительный целочисленный вес так, чтобы количество хороших вершин в дереве было максимально возможным. Если есть несколько способов сделать это, вам нужно найти такой, который минимизирует сумму весов всех вершин в дереве.
Выходные данные
В первой строке выведите два целых числа: максимальное количество хороших вершин и минимально возможный суммарный вес вершин при этом.
Во второй строке выведите \(n\) целых чисел \(w_1, w_2, \ldots, w_n\) (\(1\le w_i\le 10^9\)) — веса вершин. Можно показать, что существует оптимальное решение, удовлетворяющее данным ограничениям.
Если существует несколько решений, выведите любое из них.
Примечание
Ниже изображено дерево из первого примера:
В этом случае, если вы выберете для каждый вершины вес
\(1\), то хорошими вершинами будут вершины (покрашены черным)
\(1\),
\(3\) и
\(4\). Невозможно выбрать такие веса, чтобы все вершины были хорошими. Минимально возможная сумма весов равна
\(1+1+1+1=4\), меньшая сумма недостижима, так как вершины обязаны иметь положительный вес.
Ниже изображено дерево из второго примера:
В этом случае, если вы выберете для каждой вершины вес
\(1\), то хорошими вершинами будут вершины (покрашены черным)
\(2\) и
\(3\). Можно показать, что это оптимальное решение.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
2 3
2 4
|
3 4
1 1 1 1
|
|
2
|
3
1 2
1 3
|
2 3
1 1 1
|
|
3
|
2
1 2
|
2 2
1 1
|
|
4
|
9
3 4
7 6
2 1
8 3
5 6
1 8
8 6
9 6
|
6 11
1 1 1 1 1 1 1 3 1
|