Дано орієнтований граф з \(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\)), що вказують стартові вершини обох фішок. Для кожного запиту наведіть, який гравець виграє.

Формат вхідних даних

Перший рядок містить \(N\) та \(M\).

Кожен із наступних \(M\) рядків містить по два числа \(a\) і \(b\), що позначають дугу з \(a\) до \(b\).

Заданий граф не містить петель та множинних дуг.

Наступний рядок містить \(Q\).

Кожен з наступних \(Q\) рядків містить два цілих числа \(x\) і \(y\) (\(1\le x,y\le N\) and \(x\neq y\)), що вказують стартові вершини фішок.

Формат вихідних даних

Рядок довжиною \(Q\) де кожен символ B означає, що виграв brain, а символ H означає, що виграв hoof.

Примітка: Час на тест для цього завдання 4 сек (в два рази більше значення за замовчуванням).

Приклад вхідних даних

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

brain може виграти першу гру, вибравши вершину 5 - у hoof немає коректних ходів.

brain може виграти останню гру, вибравши вершину 4 і потім вершину 7, після чого у hoof немає коректних ходів.

Інші ігри виграє hoof.

ОЦІНЮВАННЯ:

• У тестах 2-3 \(N\le 100\), \(M\le 200\).
• У тестах 4-9 \(N\le 5000\).
• У тестах 10-21 немає додаткових обмежень.