EZGAME

Xem PDF



Tác giả:
Dạng bài
Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: EZGAME.inp Output: EZGAME.out

Cho \(G\) là một đồ thị có hướng không có chu trình, các đỉnh được đánh số từ \(1\). Có một đồng xu màu trắng đặt ở đỉnh \(w\) và một đồng xu màu đen đặt ở đỉnh \(b\). Hai người chơi một trò chơi trên \(G\) như sau:

  • Hai người chơi luân phiên nhau thực hiện lượt chơi.
  • Đến lượt mình, người chơi chọn một đồng xu bất kỳ và di chuyển nó. Nếu đồng xu màu trắng thì phải di chuyển theo các cung của đồ thị. Nếu đồng xu màu đen thì phải di chuyển ngược các cung của đồ thị. Tức là có thể di chuyển đồng xu màu trắng từ \(x\) sang \(y\) nếu \((x, y)\) là một cung của đồ thị, và có thể di chuyển đồng xu màu đen từ \(u\) sang \(v\) nếu \((v, u)\) là một cung của đồ thị.
  • Ai không thực hiện được lượt chơi hợp lệ nữa sẽ thua cuộc. Rõ ràng là trò chơi sẽ kết thúc sau hữu hạn bước, nên sẽ không có kết quả hòa.
  • Nếu người chơi biết mình sẽ thắng, anh ta sẽ cố gắng thắng nhanh nhất có thể (cực tiểu hóa số lượt chơi).
  • Nếu người chơi biết mình sẽ thua, anh ta sẽ cố gắng kéo dài thời gian (cực đại hóa số lượt chơi)

Biết rằng hai người chơi đều rất thông minh, hãy xác định số lượt chơi sẽ được thực hiện trong trò chơi.

Input

  • Dòng đầu tiên chứa \(n\), \(m\), \(w\), \(b\) (\(1 \leq n, m \leq 5000\), \(1 \leq w, b \leq n\)) là số đỉnh, số cung, vị trí của đồng xu màu trắng, vị trí của đồng xu màu đen.
  • \(m\) dòng tiếp theo mỗi dòng chứa một cung \(u\), \(v\) (\(1 \leq u, v \leq n\)).

Output

  • Ghi một số nguyên là số lượt chơi sẽ được thực hiện.

Scoring

  • Subtask 1 (\(50\%\) số điểm): Đỉnh \(b\) không có cung đi vào.
  • Subtask 2 (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input
9 11 3 3 
1 2
2 3 
3 4 
4 5 
5 6 
1 3 
3 6 
1 7 
7 8 
8 9 
9 3
Output
5

Bình luận

Không có bình luận nào.