题目描述

小度家的汽修厂是一个树形结构，有 $n$ 个节点，每个节点停放了一辆车，每一辆车都是粉色或其它颜色的。

小度想将粉色的车都停在一起，然后剪切掉一条树边，使得粉色的车在同一个连通块，其他颜色的车在另一个连通块。

每 $1$ 个单位时间，小度都可以交换两个相邻节点上的车，剪切树边不需要消耗时间，他想知道做到上述要求最少需要几个单位时间？若无解则输出 -1。

输入格式

第一行输入一个整数 $n(1≤n≤5×10^5)$ 表示汽车数量；

第二行输入一个长度为 $n$ 的字符串，$s$ 表示车的颜色，第 $i$ 个节点上的车的颜色为 $s_i$，若 $s_i$ 为 P 表示车的颜色为粉色，若 $s_i$ 为 O 则表示车的颜色为其他颜色；

接下来 $n−1$ 行，每行输入两个整数 $u,v(1≤u,v≤n)$ 表示树上的边。

输出格式

3
POP
1 2
2 3

1

解释 #1

交换 $1,2$ 节点上的车，因此只需要 $1$ 个单位时间。

4
POOP
1 2
1 3
1 4

-1

解释 #2

任意一种方案都无法满足要求。