У Владислава есть сын, который очень хотел поступить в МИТ. Общежитие колледжа в МИТ (Молдавский институт технологий) можно представить в виде дерева с \(n\) вершинами, где каждая вершина представляет собой комнату с ровно одним студентом. Дерево — это связный неориентированный граф с \(n\) вершинами и \(n-1\) ребром.
Сегодня ночью есть три типа студентов:
- студенты, которые хотят веселиться и слушать музыку (обозначены \(\texttt{P}\)),
- студенты, которые хотят спать и наслаждаться тишиной (обозначены \(\texttt{S}\)), и
- студенты, которым не важно, что делать ночью (обозначены \(\texttt{C}\)).
Изначально все рёбра представляют собой тонкие стены, которые позволяют музыке проходить через них, поэтому когда веселящийся студент включает музыку, её можно услышать в каждой комнате. Однако мы можем установить толстые стены на любые рёбра — толстые стены не позволяют музыке проходить через них.
Университет хочет установить несколько толстых стен, чтобы каждый веселящийся студент мог слушать музыку, и ни один спящий студент не мог её услышать.
Поскольку университет потерял много денег в судебном процессе о правах на наименование, они просят вас найти минимальное количество толстых стен, которые им придется использовать.
Выходные данные
Для каждого набора входных данных выведите одно целое число — искомое минимальное количество толстых стен.
Примечание
В первом случае мы можем установить одну толстую стену между комнатами \(1\) и \(2\), как показано ниже. Мы не можем установить \(0\) стен, так как тогда музыка из комнаты 3 дойдет до комнаты 2, где студент хочет спать, поэтому ответ равен \(1\). Существуют и другие допустимые решения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1 1
CSP
4
1 2 2
PCSS
4
1 2 2
PPSS
|
1
1
2
|