← 返回题目列表

Codeforces · 1266/H

H. 红蓝图

中文机器翻译题面 查看原题

在 $$$n$$$ 顶点上有一个有向图,编号为 $$$1$$$ 到 $$$n$$$,其中每个顶点($$$n$$$ 除外)都有两个向外的弧,红色和蓝色。在任何时间点,每个顶点都有一条弧处于活动状态。最初,所有蓝色弧线均处于活动状态,并且顶点 $$$1$$$ 处有一个标记。一秒钟内,带有令牌的顶点首先切换其活动弧 - 非活动弧变为活动弧,反之亦然。然后,令牌沿着活动弧移动。当令牌到达顶点 $$$n$$$ 时,它停止。保证$$$n$$$ 可以通过每个顶点的弧到达。

您收到 $$$q$$$ 查询。每个查询都包含图的一个状态 - 一对 $$$(v, s)$$$,其形式如下:

- $$$v$$$ 是令牌当前所在的顶点;
- $$$s$$$ 是由 $$$n - 1$$$ 个字符组成的字符串。第 $$$i$$$ 个字符对应于从第 $$$i$$$ 个顶点引出的活动边的颜色(如果红色弧线处于活动状态,则该字符为“R”,否则该字符为“B”)。

对于每个查询,确定给定状态是否可以从初始状态到达以及此配置第一次出现。请注意,这两个操作(更改活动弧并遍历它)是原子的 - 如果状态出现在更改活动弧之后但遍历它之前,则不认为已达到状态。

输入

第一行包含一个整数 $$$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$$$ 且仅由字符 'R' 和 'B' 组成的字符串 $$$s$$$。如果来自 $$$i$$$ 的红色弧线处于活动状态,则这些字符中的第 $$$i$$$ 为“R”,否则为“B”。

输出

输出 $$$q$$$ 行,每行包含单个查询的答案。

如果第$$$i$$$个查询中的状态不可达,则输出整数$$$-1$$$。否则,输出 $$$t_i$$$ — 状态第一次出现的时间(以秒为单位,从出现时间 $$$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

注意

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

第一个 $$$19$$$ 查询表示令牌的旅程。在第 $$$19$$$ 次移动中,令牌将到达顶点 $$$6$$$。最后两个查询显示无法访问的状态。