Tree Color Flipping

You are given a tree with n nodes, numbered from 1 to n, with node 1 as the root. Initially, each node i is painted either red or black. The initial color of node i is given by a_i (where 'R' stands for red and 'B' for black). You are also given the desired color b_i for each node.

You can perform the following operation (called the "flip spell") at most once per second:

1. Choose a node and flip its color (red becomes black and black becomes red).
2. Then, exactly one second later, the flip spell propagates to the parent of that node and flips its color, and one second after that to the grandparent, and so on, until the root is reached.

A twist is that if, at the same moment, a node is targeted by several flip spells, they cancel each other pairwise. In other words, if an even number of flip spells hit a node simultaneously then no color change occurs at that moment and the propagation stops for that branch.

Assume that you may schedule the spells in such a way that cancellations do not occur (by avoiding simultaneous flips on the same node). Determine the minimum number of seconds needed so that the tree first reaches the target configuration.

Note: It can be proven that it is always possible to achieve the target configuration.

Hint: You can think of red and black as binary values (R = 1 and B = 0). An operation initiated at node v (with depth d(v)) contributes a flip (i.e. 1) to each of its ancestors, and if no two spells meet at the same time, the final color of a node v is

\( a_v \oplus \Big(\sum_{u \in \text{subtree}(v)} x_u\Big) = b_v \),

where \(x_u \in \{0,1\}\) indicates whether a flip spell is initiated at node \(u\), and the sum is taken modulo 2. Moreover, if you initiate a spell at a node at time \(t\), the effect on that node occurs immediately, and the effect on an ancestor at distance \(k\) occurs at time \(t+k\). Since you can only initiate one spell per second, think about assigning initiation times optimally to minimize the overall finishing time.

Once you decide on the set of nodes where an operation is needed, let their depths be \(d_1, d_2, \dots, d_k\). By scheduling the operations in descending order of depth (i.e. assign the earliest possible time to the deepest node), the minimum number of seconds needed is given by:

\( T = \max_{0 \le i < k} \{ i + d_i \} \)

where we assume the first operation is initiated at time 0. Your task is to compute this minimum number of seconds.

inputFormat

The input is given as follows:

 n
 a
 b
 u1 v1
 u2 v2
 ...
 u{n-1} v{n-1}

Here, n is the number of nodes in the tree. The second line is a string of length n representing the initial colors (each character is either 'R' or 'B'). The third line is a string of length n representing the target colors. Each of the following n-1 lines contains two integers u and v, indicating there is an edge between nodes u and v. The tree is rooted at node 1.

outputFormat

Output a single integer, the minimum number of seconds needed until the tree first reaches the target configuration.

sample

2
BB
RR
1 2

1

</p>