Trò Chơi Đồng Xu Trên Đồ Thị

Buổi 50 — Game Theory
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions

Đề bài

Cho đồ thị có hướng không chu trình (DAG) gồm n đỉnh và m cạnh. Có k đồng xu được đặt trên các đỉnh khác nhau v_1, v_2, ..., v_k.

Hai người chơi thay phiên nhau. Mỗi lượt, người chơi chọn một đồng xu và di chuyển nó dọc theo một cạnh có hướng đến đỉnh kề. Nhiều đồng xu có thể ở cùng một đỉnh. Người chơi nào không thể di chuyển bất kỳ đồng xu nào (tất cả đồng xu đều ở đỉnh không có cạnh đi ra) sẽ thua.

Người chơi đầu tiên đi trước. Xác định ai sẽ thắng nếu cả hai chơi tối ưu.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên n, m, k (1 ≤ n ≤ 5000, 0 ≤ m ≤ 10000, 1 ≤ k ≤ n).
  • m dòng tiếp theo, mỗi dòng chứa hai số u, v (1 ≤ u, v ≤ n) — có cạnh từ u đến v.
  • Dòng cuối chứa k số nguyên v_1, v_2, ..., v_k (1 ≤ v_i ≤ n) — vị trí các đồng xu (đôi một khác nhau).
  • Đồ thị đảm bảo là DAG.

Dữ liệu ra

  • In ra "First" nếu người chơi đầu tiên thắng, "Second" nếu người chơi thứ hai thắng.

Ví dụ

Input
4 4 2
1 2
1 3
2 4
3 4
1 2
Output
First

Giải thích

  • Grundy(4) = 0, Grundy(2) = mex{0} = 1, Grundy(3) = mex{0} = 1, Grundy(1) = mex{1,1} = mex{1} = 0.
  • Tổng XOR = Grundy(1) XOR Grundy(2) = 0 XOR 1 = 1 ≠ 0 → First thắng.

Giới hạn

  • 1 ≤ n ≤ 5000
  • 0 ≤ m ≤ 10000
  • 1 ≤ k ≤ n
  • Đồ thị là DAG
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved