Red-Blue Graph

题意翻译

给定一张 $n(2\le n\le58)$ 个点的图，除了 $n$ 号点外的每个点都有两条出边，分别被染成红色和蓝色，每个点的两条出边在任意时刻均有且仅有一条是活跃的，保证 $n$ 从任意一个点出发可达。 一开始，所有蓝边都是活跃的，你在 $1$ 号点，每秒将会**依次**发生以下事件： 1.你所处的点的两条出边活跃性交换，即活跃的边变成不活跃的，不活跃的边变成活跃的。 2.你走到活跃的边所指向的点。 如果走到 $n$ 号点则停止走动。 将会给出 $q(1\le q\le5000)$ 组询问，每组询问将会给出一个正整数 $v(1\le v<n)$ 和长为 $n-1$ 的由 `R` 和 `B` 组成字符串 $s$，表示一个你所在的点和每个点的活跃的出边的颜色的状态，你需要找出这个状态首次出现是在第几秒末，如果不存在这个状态则回答 `-1` 注意每秒中间仅进行了状态翻转操作后尚进行移动操作时出现的状态并不算“出现是在第几秒末”中的“出现”

题目描述

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.

输入输出格式

输入格式

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 < 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.

输出格式

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 $ ).

输入输出样例

输入样例 #1

6
2 1
5 5
2 1
6 3
4 3
21
1 BBBBB
1 RBBBB
2 BBBBB
5 BRBBB
3 BRBBR
1 BRRBR
1 RRRBR
2 BRRBR
5 BBRBR
4 BBRBB
3 BBRRB
2 BBBRB
5 BRBRB
3 BRBRR
1 BRRRR
1 RRRRR
2 BRRRR
5 BBRRR
4 BBRRB
2 BRBBB
4 BRBBR

输出样例 #1

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
-1
-1

说明

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.