Cho một đồ thị có hướng \(N\) đỉnh, \(M\) cạnh \((2 \le N \le 10^5, 1 \le M \le 2 \times 10^5)\), mấy con bò của bác John già chơi một trò chơi \(2\) người như sau.
Đặt hai đồng xu lên \(2\) nút khác nhau của đồ thị. Ở mỗi lượt, người chơi thứ nhất - đầu não - sẽ chọn một đồng xu và đồng xu này sẽ đi theo một cạnh sang nút khác, người chơi thứ hai - móng guốc - sẽ chọn cạnh để di chuyển đồng xu mà người thứ nhất đã chọn. Một nước không thể có hai vua, một rừng không thể có hai hổ thì một nút không thể có hai đồng xu. Do đó, nếu như móng guốc không còn nước đi hợp lệ, thì đầu não sẽ là kẻ chiến thắng. Ngược lại, nếu trò chơi không thể kết thúc, móng guốc sẽ là kẻ chiến thắng. Biết rằng cả hai đều chơi tối ưu.
Có \(Q\) \((1 \le Q \le 10^5)\) ván đấu, mỗi ván được biểu diễn bằng hai nút thể hiện vị trí ban đầu của hai đồng xu. Với mỗi ván đấu, hãy cho biết ai sẽ là người chiến thắng!!!!
Input
- Dòng đầu tiên là \(2\) số \(N\) và \(M\).
- \(M\) dòng tiếp theo, mỗi dòng là \(2\) số nguyên \(a, b\) thể hiện có cạnh nối từ \(a\) đến \(b\).
- Đồ thị thoả mãn không có khuyên và không có cạnh nào xuất hiện nhiều hơn \(1\) lần.
- Dòng tiếp theo là số \(Q\).
- \(Q\) dòng tiếp theo, mỗi dòng là hai số \(x\) và \(y\) \((1 \le x, y \le N, x \ne y)\).
Output
- \(Q\) dòng, mỗi dòng là một kí tự, trong đó
B
nếu như đầu não thắng vàH
nếu như móng guốc thắng.
Scoring
- Subtask \(1\): \(N \le 100, M \le 200\).
- Subtask \(2\): \(N \le 5000\).
- Subtask \(3\): Không có ràng buộc gì thêm.
Test 1
Input
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
Output
BHHB
Note
- Đầu não có thể chiến thắng trong ván đầu tiên bằng cách chọn đồng xu ở nút \(5\), lúc đó móng guốc không còn nước đi hợp lệ.
- Đầu não có thể chiến thắng trong ván cuối cùng bằng cách chọn đồng xu ở nút \(4\) sau đó chọn ở nút \(7\), lúc đó móng guốc không còn nước đi hợp lệ.
- Móng guốc chiến thắng trong các ván đầu còn lại.
Bình luận