在 $$$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$$$。最后两个查询显示无法访问的状态。