Móng và Não

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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 \leq N \leq 10^{5}$ , $1 \leq M \leq 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 \leq Q \leq 10^{5}$ ).
$Q$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $x$ và $y$ ( $x \neq 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 \leq N \leq 10^{5}$
$1 \leq M \leq 2 \times 10^{5}$
$1 \leq Q \leq 10^{5}$
Test 2–3: $N \leq 100$ , $M \leq 200$
Test 4–9: $N \leq 5000$
Test 10–21: không có ràng buộc thêm

Ví dụ

Input	Output	Giải thích
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	Truy vấn 1: Não thắng vì đỉnh 5 không có cạnh ra. Truy vấn 2–3: Móng có thể đi mãi vòng. Truy vấn 4: Não thắng vì đỉnh 5 (đỉnh duy nhất không có cạnh ra trong thành phần liên quan) được nối vào chuỗi từ đỉnh 4.

Bình luận

Không có bình luận tại thời điểm này.