H. Красно-синий граф
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан ориентированный граф из $$$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$$$) и строку $$$s$$$ из $$$n-1$$$ символов, каждый из которых либо 'R', либо 'B'. $$$i$$$-й из этих символов равен 'R', если красная дуга, ведущая из вершины $$$i$$$, активна, иначе этот символ равен 'B'.

Выходные данные

Выведите $$$q$$$ чисел, каждое из которых содержит ответ на один запрос.

Если состояние в $$$i$$$-м запросе недостижимо, выведите $$$-1$$$. Иначе выведите $$$t_i$$$ — первый момент времени, когда это состояние появилось (выводите время в секундах, начиная отсчет с секунды $$$0$$$, в которую появилось стартовое состояние).

Пример
Входные данные
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
Выходные данные
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
-1
-1
Примечание

На картине изображен граф из первого примера.

Первые $$$19$$$ запросов показывают перемещение фишки. После $$$19$$$-го шага фишка достигает вершины $$$6$$$. Последние два запроса соответствуют недостижимым состояниям.