Задано неориентированное дерево из \(n\) вершин.
Некоторые вершины покрашены в красный цвет, некоторые — в синий, а некоторые не покрашены совсем. Гарантируется, что дерево содержит хотя бы одну красную вершину и хотя бы одну синюю вершину.
Вы выбираете ребро и удаляете его из дерева. Дерево распадается на две связных компоненты. Назовем ребро хорошим, если в каждой из двух компонент не будет одновременно синей и красной вершин.
Сколько хороших ребер в данном дереве?
Выходные данные
Выведите одно целое число — количество хороших ребер в данном дереве.
Примечание
Дерево из первого примера:
Единственное хорошее ребро — это ребро \((2, 4)\). После его удаления дерево распадается на компоненты \(\{4\}\) и \(\{1, 2, 3, 5\}\). В первой компоненте есть только красная вершина, а во второй — только синие и непокрашенные вершины.
Дерево из второго примера:
Каждое ребро в нем хорошее.
Дерево из третьего примера:
Ребро \((1, 3)\) разделяет дерево на компоненты \(\{1\}\) и \(\{3, 2\}\), во второй есть одновременно красная и синяя вершины, поэтому это ребро не хорошее. Ребро \((2, 3)\) разделяет дерево на компоненты \(\{1, 3\}\) и \(\{2\}\), в первой есть одновременно красная и синяя вершины, поэтому это ребро также не хорошее. Потому ответ равен 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 0 0 1 2
1 2
2 3
2 4
2 5
|
1
|
|
2
|
5
1 0 0 0 2
1 2
2 3
3 4
4 5
|
4
|
|
3
|
3
1 1 2
2 3
1 3
|
0
|