You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目内容

曾经有一个叫做塔子哥的年轻人，他是一个热衷于研究二叉树的数学家。他认为，一棵树只有当它的红色节点数量大于蓝色节点数量时才是好树。他的定义引起了人们的热议，有些人同意他的定义，有些人则持不同意见。但无论怎样，这个定义还是被广泛地接受了。

有一天，塔子哥发现了一棵好树，但他觉得它不够完美。于是他开始思考，如果能够将这棵好树分成两个好树，那它就更加完美了。

经过一番研究，他发现只需要删除一条边，就可以将这棵树分成两个好树。他想知道有多少种删除边的方案，于是他向你求助。

输入描述

第一行输入一个正整数 $n$ ，代表节点的数量。

第二行输入一个长度为 $n$ 的，仅包含 'R' 和 'B' 两种字符的字符串，第 $i$ 个字符为 'R' 代表第 $i$ 个节点被染成红色，'B'代表被染成蓝色。

接下来的 $n -1$ 行，每行输入两个正整数 $u$ 和 $v$ ，代表节点 $u$ 和节点 $v$ 有一条边连接。

$1\le n\le 10^5$

输出描述

一个整数，代表删边的方案数。

样例

输入

5
RRBRB
1 2
2 3
1 4
4 5

输出

0

样例解释

无论删除哪条边，都会导致有一个子树不是好树。