Móng và Não

Cho một đồ thị có hướng gồm $N$ đỉnh và $M$ cạnh. Hai người chơi Não và Móng cùng đặt hai quân cờ trên đồ thị (quân của mỗi người tại một đỉnh khác nhau). Họ thực hiện các bước đi luân phiên nhau như sau: mỗi bước, Não chọn một trong hai quân cờ, rồi Móng phải di chuyển quân cờ đó dọc theo một cạnh ra của đỉnh đó.

Quy tắc chiến thắng:

• Não thắng nếu Móng không thể di chuyển (quân cờ được chọn đang ở đỉnh không có cạnh ra, hoặc cạnh ra duy nhất dẫn đến đỉnh có quân còn lại).
• Móng thắng nếu trò chơi kéo dài mãi mãi.

Hai quân cờ không được phép cùng đứng trên một đỉnh. Nếu Móng bị buộc di chuyển đến đỉnh có quân kia, trò chơi kết thúc và Não thắng (vì Móng không có nước đi hợp lệ).

Cho $Q$ truy vấn, mỗi truy vấn cho hai đỉnh xuất phát $(x,y)$ của hai quân cờ, hãy xác định ai thắng khi cả hai chơi tối ưu.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$ và $M$ ($2\le N\le {10}^5$, $1\le M\le 2\times {10}^5$).
• $M$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $a$ và $b$ — cạnh có hướng từ $a$ đến $b$.
• Dòng tiếp theo: số nguyên $Q$ ($1\le Q\le {10}^5$).
• $Q$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $x$ và $y$ ($x\ne y$) — vị trí xuất phát của hai quân cờ.

Đồ thị không có khuyên và không có cạnh bội.

Dữ liệu ra

Một xâu ký tự độ dài $Q$. Ký tự thứ $i$ là B nếu Não thắng truy vấn thứ $i$, ngược lại là H.

Ràng buộc

• $2\le N\le {10}^5$
• $1\le M\le 2\times {10}^5$
• $1\le Q\le {10}^5$
• Test 2–3: $N\le 100$, $M\le 200$
• Test 4–9: $N\le 5000$
• Test 10–21: không có ràng buộc thêm

Ví dụ