Дан ориентированный граф с \(N\) вершинами и \(M\) дугами (\(2 \leq N \leq 10^5\),
\(1 \leq M \leq 2 \cdot 10^5\)). Коровы играют в такую игру для двух игроков:
Две фишки размещаются на заданном графе.
На каждом ходу первый игрок (brain) выбирает фишку, которая должна пройти по
одной из выходящих дуг. Другой игрок (hoof) выбирает по какой дуге должна
пойти эта фишка. Эти две фишки никогда не могут быть в одной и той же вершине.
Если в какой-то момент hoof не может сделать ход, выиграл brain. Если игра
продолжается бесконечно - выиграл hoof.
Вам даются \(Q\) запросов (\(1 \leq Q \leq 10^5\)), указывающие стартовые вершины
обоих фишек. Для каждого запроса выведите, какой игрок выиграет.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) и
\(M\).
Каждая из последующих \(M\) строк содержит по два числа \(a\) и \(b\), обозначающих
дугу из \(a\) в \(b\).
Заданный граф не содержит петель и множественных дуг.
Следующая строка содержит \(Q\).
Каждая из последующих \(Q\) строк содержит два целых числа \(x\) и \(y\)
(\(1\le x,y\le N\) and \(x\neq y\)), указывающих стартовые вершины фишек.
ФОРМАТ ВЫВОДА (на экран / stdout):
Строка длиной \(Q\) где каждый символ B означает, что выиграл brain, а символ H
означает, что выиграл hoof.
**Замечание: Время на тест для этой задачи 4 сек, (в два раза больше значения по умолчанию).**
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9 10
1 2
2 3
3 4
4 7
3 5
1 6
6 8
8 9
9 6
7 2
4
1 5
1 2
1 6
2 4
|
BHHB
|