- Описание
- Отправленные решения
203. Страна с разноцветными дорогами
В Светофорляндии разработана самая революционная дорожно-транспортная система. Одним из нововведений стали разноцветные однонаправленные дороги. Дорога может быть покрашена в зелёный, жёлтый или красный.
Президент страны вызвал своего советника Дормидонта, чтобы спланировать путешествие по стране. Президент задает Дормидонту $q$ вопросов: сколько существует различных путей между городом $a_i$ и $b_i$, где первая дорога - зелёная, вторая - жёлтая, а третья - красная. Дормидонт растерялся и просит вашей помощи. Пути считаются разными, если отличаются хотя бы одним ребром. Города в пути могут повторяться.
Формат ввода
На первой строке находятся два числа, разделённых пробелом - количество городов $n \le 500$ и количество дорог $m \le 750000$ в Светофорляндии.
Далее идут $m$ строк, описывающих дороги. Каждая из этих $m$ строк содержит 2 числа и один символ, разделённые пробелом, где первое число - номер города, из которого выходит дорога, второе число - город, в который ведет дорога, и символ, описывающий цвет дороги ('g' - обозначение зелёной дороги, 'y' - обозначение жёлтой дороги или 'r' - обозначение красной дороги).
Следующая строка содержит единственное число $q \le 250000$ - количество вопросов президента. Каждая из следующих $q$ строк содержит два числа, разделённых пробелом: номер города, в котором президент планирует начать путешествие и номер города, в котором президент планирует закончить путешествие.
Формат вывода
Выведете $q$ строк, в каждой по одному числу - ответ на $i$-ый вопрос президента.
Ограничения
Ограничение времени
5 с
Ограничение памяти
512 МБ
Пример 1
10 6
7 4 g
4 10 y
10 9 r
1 3 g
3 5 y
5 2 r
24
7 9
1 2
10 1
5 1
10 5
8 9
5 9
8 5
10 8
2 9
3 9
10 8
10 8
7 10
2 6
9 4
1 5
4 10
1 8
7 4
10 3
2 4
3 3
2 4
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Пример 2
10 6
6 7 g
7 3 y
3 10 r
8 1 g
1 5 y
5 9 r
18
6 10
8 9
6 4
2 3
4 6
2 6
5 8
6 10
9 6
6 2
5 1
5 5
9 5
2 8
1 3
1 10
4 10
8 3
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0