CF1266H.Red-Blue Graph

There is a directed graph on $n$ vertices numbered $1$ through $n$ where each vertex (except $n$) has two outgoing arcs, red and blue. At any point in time, exactly one of the arcs is active for each vertex. Initially, all blue arcs are active and there is a token located at vertex $1$. In one second, the vertex with token first switches its active arcs — the inactive arc becomes active and vice versa. Then, the token is moved along the active arc. When the token reaches the vertex $n$, it stops. It is guaranteed that $n$ is reachable via arcs from every vertex.

You are given $q$ queries. Each query contains a state of the graph — a pair $(v, s)$ of the following form:

• $v$ is the vertex where the token is currently located;
• $s$ is a string consisting of $n - 1$ characters. The $i$-th character corresponds to the color of the active edge leading from the $i$-th vertex (the character is 'R' if red arc is active, otherwise the character is 'B').

For each query, determine whether the given state is reachable from the initial state and the first time this configuration appears. Note that the two operations (change active arc and traverse it) are atomic — a state is not considered reached if it appears after changing the active arc but before traversing it.

存在一个有向图，其顶点编号为 $1$ 到 $n$。除顶点 $n$ 外，每个顶点均恰好有两条出边：一条红色边与一条蓝色边。在任意时刻，每个顶点（除 $n$ 外）的两条出边中恰有一条处于激活状态。初始时，所有顶点的蓝色边均被激活，且一个标记（token）位于顶点 $1$ 上。每秒钟执行如下操作：

• 首先，当前持有标记的顶点切换其激活边（即原未激活边变为激活，原激活边变为未激活）；
• 然后，将标记沿该顶点当前激活的边移动至下一个顶点。

当标记到达顶点 $n$ 时，过程终止。题目保证从任意顶点出发，均可经若干条边到达顶点 $n$。

现给出 $q$ 个查询。每个查询描述图的一个状态，形式为一对 $(v, s)$，其中：

• $v$ 表示标记当前所在的顶点；
• $s$ 是一个长度为 $n - 1$ 的字符串。第 $i$ 个字符对应于从第 $i$ 个顶点出发的激活边的颜色（若为红色边激活，则该字符为 'R'；否则为 'B'）。

对每个查询，请判断该状态是否可从初始状态到达；若可达，还需输出该状态首次出现的时间（以秒为单位）。注意：上述两个操作（切换激活边、沿激活边移动标记）是原子性的——仅当完成整套操作（即切换后立即移动）后所得到的状态才被视为“到达”；若仅完成切换但尚未移动标记，则该中间状态不视为到达。

The first line contains a single integer $n$ ($2 \leq n \leq 58$) — the number of vertices.

$n-1$ lines follow, $i$-th of contains two space separated integers $b_i$ and $r_i$ ($1 \leq b_i, r_i \leq n$) representing a blue arc $(i, b_i)$ and red arc $(i, r_i)$, respectively. It is guaranteed that vertex $n$ is reachable from every vertex.

The next line contains a single integer $q$ ($1 \leq q \leq 5000$) — the number of queries.

Then $q$ lines with queries follow. The $j$-th of these lines contains an integer $v$ ($1 \leq v \lt n$) and a string $s$ of length $n-1$ consiting only of characters 'R' and 'B'. The $i$-th of these characters is 'R' if the red arc going from $i$ is active and 'B' otherwise.

第一行包含一个整数 $n$（$2 \leq n \leq 58$）—— 表示顶点数量。

接下来 $n-1$ 行，第 $i$ 行包含两个以空格分隔的整数 $b_i$ 和 $r_i$（$1 \leq b_i, r_i \leq n$），分别表示一条蓝色有向边 $(i, b_i)$ 和一条红色有向边 $(i, r_i)$。保证从任意顶点出发均能到达顶点 $n$。

下一行包含一个整数 $q$（$1 \leq q \leq 5000$）—— 表示查询次数。

随后是 $q$ 行查询。第 $j$ 行包含一个整数 $v$（$1 \leq v < n$）和一个长度为 $n-1$ 的字符串 $s$，该字符串仅由字符 'R' 和 'B' 组成。其中第 $i$ 个字符为 'R' 表示从顶点 $i$ 出发的红色有向边处于激活状态，为 'B' 则表示该红色有向边未激活（即此时使用蓝色有向边）。

Output $q$ lines, each containing answer to a single query.

If the state in the $i$-th query is unreachable, output the integer $-1$. Otherwise, output $t_i$ — the first time when the state appears (measured in seconds, starting from the initial state of the graph which appears in time $0$).

输出 $q$ 行，每行包含一个查询的答案。

如果第 $i$ 个查询所对应的状态不可达，则输出整数 $-1$；否则，输出 $t_i$ —— 该状态首次出现的时间（以秒为单位，起始时刻为图的初始状态，对应时间为 $0$）。

The graph in the first example is depticed in the figure below.

The first $19$ queries denote the journey of the token. On the $19$-th move the token would reach the vertex $6$. The last two queries show states that are unreachable.

第一个示例中的图如下所示。

前 $19$ 个查询表示令牌的行进路径。在第 $19$ 次移动后，令牌将到达顶点 $6$。最后两个查询表示无法到达的状态。