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

Buổi 50 — Game Theory
Points
25
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. Một quân cờ được đặt tại đỉnh s. Hai người chơi thay phiên nhau di chuyển quân cờ dọc theo một cạnh có hướng. Người chơi nào không thể di chuyển (đỉnh hiện tại 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, s (1 ≤ n ≤ 5000, 0 ≤ m ≤ 5000, 1 ≤ s ≤ n) — số đỉnh, số cạnh, đỉnh xuất phát.
  • 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.
  • Đồ thị đảm bảo là DAG (không có chu trình).

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 1
1 2
1 3
2 4
3 4
Output
First

Giải thích

  • Đỉnh 4 không có cạnh đi ra, Grundy(4) = 0.
  • Grundy(2) = mex{0} = 1, Grundy(3) = mex{0} = 1.
  • Grundy(1) = mex{1, 1} = 0? Không, mex{1} = 0. Nhưng thực tế Grundy(1) = mex{Grundy(2), Grundy(3)} = mex{1, 1} = mex{1} = 0.
  • Ồ, nhưng kết quả là First. Hãy xét lại: từ đỉnh 1 đi đến 2, từ 2 đi đến 4, đối thủ kẹt tại 4. First thắng vì đường đi dài 2 (chẵn lượt).
  • Grundy(4)=0, Grundy(2)=mex{0}=1, Grundy(3)=mex{0}=1, Grundy(1)=mex{1,1}=mex{1}=0.
  • Grundy(1)=0 → Second thắng? Xin lỗi, kết quả đúng là Second.
Input
4 4 1
1 2
1 3
2 4
3 4
Output
Second

Giới hạn

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