Задача 4. Фантастическое чёрно-красное дерево ≡

Условие

Существует фантастическое черное-красное дерево - граф, который представляет из себя дерево (связный граф без циклов), в котором каждая вершина покрашена в один из двух цветов - красный или черный.

У вас есть не менее замечательная строка s, состоящая из K символов ‘r' и 'b’. Ваша задача - выяснить сколько существует путей по дереву, таких, что если выписать цвета вершин, по которым вы прошлись, то получится строка s.

Путь - последовательность вершин, которая ведет из одной вершины в другую и проходит по ребрам графа. Одна вершина встречается в пути не более одного раза.

Формат входных данных

В первой строке целое число N- количество вершин в графе.

Далее строка g состоящая из N символов ‘r' и 'b’, описывающая цвета вершин дерева.

Далее строка s, состоящая из K символов ‘r' и 'b’.

В следующих строках два целых числа - a_i и b_i - начало и конец ребра.

Формат выходных данных

Ограничения

2 ≤ K ≤ N ≤ 10⁴

Примеры тестов

5
brbrr
rbr
1 3
4 3
3 5
2 3

6

5
brrbr
rb
1 2
1 5
3 4
5 4

4

Разбор

Для каждой вершины запустим алгоритм поиска:

Если цвет вершины и цвет текущего символа в строке не равны: return; Если текущая глубина обхода равна длине строки: увеличиваем переменную ответа на 1. Заходим во все вершины, кроме той, из которой пришли.

Для каждой вершины мы заходим максимум во все вершины. O(n^2)