Trò chơi quân cờ trên DAG
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một đồ thị có hướng không chu trình (DAG) gồm $N$ đỉnh và $M$ cạnh. Trên đồ thị có $P$ quân cờ đặt tại các đỉnh $s_1, s_2, \dots, s_P$ (một đỉnh có thể chứa nhiều quân cờ).
Hai người chơi An và Bình luân phiên đi nước, An đi trước. Ở mỗi lượt, người chơi chọn một quân cờ bất kỳ và di chuyển nó dọc theo một cạnh có hướng từ đỉnh hiện tại sang đỉnh kề. Ai không thể di chuyển quân cờ nào nữa sẽ thua.
Biết cả hai đều chơi tối ưu, hãy xác định người thắng cuộc. In ra AN nếu An thắng, ngược lại in ra BINH.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, M, P$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$, $1 \le P \le 10^5$).
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả cạnh có hướng từ $u$ đến $v$.
- Dòng cuối cùng chứa $P$ số nguyên $s_1, s_2, \dots, s_P$ ($1 \le s_i \le N$).
Dữ liệu ra
- In ra
ANhoặcBINH.
Ví dụ
| Input | Output |
|---|---|
| 4 4 2 1 2 1 3 2 4 3 4 1 2 |
AN |
Giới hạn
- $1 \le N, P \le 10^5$, $0 \le M \le 2 \cdot 10^5$
Community Discussion