Trò Chơi Trên Đồ Thị Có Hướng
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho đồ thị có hướng không chu trình (DAG) gồm N đỉnh và M cạnh. Một quân cờ đặt tại đỉnh S. An và Bình chơi luân phiên, An đi trước. Mỗi lượt, người chơi phải di chuyển quân cờ theo một cạnh ra khỏi đỉnh hiện tại. Người không thể di chuyển thua.
Cho Q truy vấn, mỗi truy vấn cho đỉnh xuất phát S. Hãy xác định ai thắng nếu cả hai chơi tối ưu.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên N M (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000).
M dòng tiếp theo, mỗi dòng chứa hai số nguyên u v (1 ≤ u, v ≤ N) mô tả cạnh có hướng từ u đến v.
Dòng tiếp theo chứa số nguyên Q (1 ≤ Q ≤ 100000).
Q dòng tiếp theo, mỗi dòng chứa số nguyên S (1 ≤ S ≤ N).
Dữ liệu ra
Với mỗi truy vấn, in "An" nếu An thắng, "Binh" nếu Bình thắng.
Ví dụ
| Input | Output |
|---|---|
| 4 4\n1 2\n1 3\n2 4\n3 4\n3\n1\n2\n4 | An\nAn\nBinh |
Giới hạn
- 1 ≤ N ≤ 100000
- 0 ≤ M ≤ 200000
- Đồ thị là DAG
- 1 ≤ Q ≤ 100000
Community Discussion