| Автор: | Завгороднев А.А., Бадерик М.М. | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
| Выходной файл: | Стандартный выход |
Существует фантастическое черное-красное дерево - граф, который представляет из себя дерево (связный граф без циклов), в котором каждая вершина покрашена в один из двух цветов - красный или черный.
У вас есть не менее замечательная строка s, состоящая из K символов ‘r' и 'b’. Ваша задача - выяснить сколько существует путей по дереву, таких, что если выписать цвета вершин, по которым вы прошлись, то получится строка s.
Путь - последовательность вершин, которая ведет из одной вершины в другую и проходит по ребрам графа. Одна вершина встречается в пути не более одного раза.
В первой строке целое число N- количество вершин в графе.
Далее строка g состоящая из N символов ‘r' и 'b’, описывающая цвета вершин дерева.
Далее строка s, состоящая из K символов ‘r' и 'b’.
В следующих строках два целых числа - ai и bi - начало и конец ребра.
2 ≤ K ≤ N ≤ 104
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|