Trò Chơi Trên Đồ Thị Có Hướng

Buổi 52 — Mock Contest Phase 2
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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
Draft saved