Дан ориентированный граф из \(n\) вершин, пронумерованных от \(1\) до \(n\), в котором из каждой вершины (кроме \(n\)) исходит две дуги, красная и синяя. В любой момент времени ровно одна исходящая дуга является активной для каждой вершины. Изначально все синие дуги активны, а в вершине \(1\) находится фишка. В начале каждой секунды у вершины, в которой стоит фишка, меняется активная дуга. Затем фишка перемещается по активной дуге. Когда фишка достигает вершины \(n\), она останавливается. Гарантируется, что вершина \(n\) достижима по дугам из всех остальных вершин графа.
Вам задаются \(q\) запросов, в каждом из которых описывается состояние графа — пара \((v, s)\) следующего вида:
- \(v\) — вершина, в которой находится фишка;
- \(s\) — строка из \(n - 1\) символов. \(i\)-й символ обозначает, какая дуга, ведущая из \(i\), активна (красная, если символ равен 'R', или синяя, если символ — 'B').
Для каждого запроса определите, достижимо ли заданное состояние из стартового, и если да — когда такое состояние графа появится в первый раз. Обратите внимание, что заданные две операции неразрывны между собой — состояние не считается достигнутым, если оно появляется после изменения активной дуги, но до того, как фишку переместили по дуге.
Выходные данные
Выведите \(q\) чисел, каждое из которых содержит ответ на один запрос.
Если состояние в \(i\)-м запросе недостижимо, выведите \(-1\). Иначе выведите \(t_i\) — первый момент времени, когда это состояние появилось (выводите время в секундах, начиная отсчет с секунды \(0\), в которую появилось стартовое состояние).
Примечание
На картине изображен граф из первого примера.
Первые \(19\) запросов показывают перемещение фишки. После \(19\)-го шага фишка достигает вершины \(6\). Последние два запроса соответствуют недостижимым состояниям.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
-1
-1
|