Thắng, thua hay hòa trên đồ thị (Graph Game)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một đồ thị có hướng gồm $N$ đỉnh, được đánh số từ $1$ đến $N$, và $M$ cạnh có hướng.

Một quân cờ được đặt trên một đỉnh của đồ thị. Hai người chơi lần lượt thực hiện các lượt đi trên cùng quân cờ đó.

Ở mỗi lượt, giả sử quân cờ hiện đang nằm tại đỉnh $u$:

• người đang đến lượt phải chọn một cạnh đi ra từ $u$;
• nếu chọn cạnh $u\rightarrow v$, quân cờ được chuyển từ đỉnh $u$ sang đỉnh $v$;
• sau đó lượt chơi được chuyển cho đối thủ.

Nếu đến lượt một người chơi mà quân cờ đang ở một đỉnh không có bất kỳ cạnh đi ra nào, người chơi đó không thể thực hiện nước đi và thua ngay lập tức.

---

Đồ thị có thể chứa chu trình. Vì vậy, khác với trò chơi trên cây hoặc trên đồ thị không chu trình, một ván chơi không nhất thiết phải kết thúc.

Ví dụ, nếu quân cờ liên tục di chuyển theo một chu trình

$$u_1\rightarrow u_2\rightarrow\cdots\rightarrow u_k\rightarrow u_1,$$

thì ván chơi có thể tiếp tục mãi mà không có người nào rơi vào một đỉnh không còn nước đi.

Do đó, một trạng thái của trò chơi có thể có ba kết quả khác nhau: thắng, thua hoặc hòa.

---

Với mỗi đỉnh $v$, hãy tưởng tượng rằng ta bắt đầu một ván chơi mới như sau:

• quân cờ ban đầu nằm tại đỉnh $v$;
• một người chơi đang đến lượt tại $v$;
• cả hai người chơi đều chơi tối ưu, nghĩa là mỗi người luôn cố gắng đạt kết quả tốt nhất có thể cho mình.

Kết quả của trạng thái tại đỉnh $v$ được định nghĩa theo góc nhìn của người đang đến lượt tại chính đỉnh đó.

Trạng thái WIN

Đỉnh $v$ được gọi là WIN nếu người đang đến lượt tại $v$ có ít nhất một cách chơi để buộc đối thủ thua, bất kể đối thủ lựa chọn các nước đi như thế nào sau đó.

Nói cách khác, người đang đến lượt có thể đảm bảo chiến thắng.

Trạng thái LOSE

Đỉnh $v$ được gọi là LOSE nếu người đang đến lượt tại $v$ không thể tránh khỏi thất bại khi đối thủ chơi tối ưu.

Đặc biệt, mọi đỉnh không có cạnh đi ra đều là trạng thái LOSE, bởi người đang đến lượt không thể thực hiện bất kỳ nước đi nào.

Trạng thái DRAW

Đỉnh $v$ được gọi là DRAW nếu:

• người đang đến lượt không thể buộc thắng;
• đối thủ cũng không thể buộc người đó thua;
• với cách chơi tối ưu, ván chơi có thể được duy trì vô hạn.

Trong trường hợp này, không người chơi nào có thể ép ván đấu đi đến một trạng thái mà đối thủ chắc chắn thua.

---

Cần lưu ý rằng WIN và LOSE không chỉ một người chơi cố định.

Ví dụ, nếu đỉnh $v$ là WIN, điều đó có nghĩa là:

người nào đang đến lượt khi quân cờ ở $v$ có thể buộc thắng.

Tương tự, nếu đỉnh $v$ là LOSE, người đang đến lượt tại $v$ sẽ thua nếu đối thủ chơi tối ưu.

---

Ban đầu quân cờ được đặt tại đỉnh $S$.

Hãy xác định:

1. kết quả của trạng thái bắt đầu tại đỉnh $S$;
2. kết quả của trạng thái bắt đầu tại từng đỉnh $1,2,\ldots,N$.

Input

Dòng đầu tiên chứa ba số nguyên $N$, $M$, $S$:

• $N$ là số đỉnh của đồ thị;
• $M$ là số cạnh có hướng;
• $S$ là đỉnh đặt quân cờ trong trạng thái ban đầu cần xét.

Mỗi trong $M$ dòng tiếp theo chứa hai số nguyên $u$, $v$, biểu diễn một cạnh có hướng

$$u\rightarrow v.$$

Điều này có nghĩa là nếu quân cờ đang ở đỉnh $u$, người đang đến lượt có thể chọn nước đi đưa quân cờ sang đỉnh $v$.

Đồ thị có thể:

• có nhiều thành phần;
• chứa chu trình;
• có đỉnh không có cạnh đi ra;
• có đỉnh có nhiều lựa chọn nước đi.

Output

Dòng đầu tiên in kết quả của trạng thái bắt đầu tại đỉnh $S$:

• in WIN nếu người đang đến lượt tại $S$ có thể buộc thắng;
• in LOSE nếu người đang đến lượt tại $S$ chắc chắn thua khi đối thủ chơi tối ưu;
• in DRAW nếu không bên nào có thể buộc thắng và ván chơi có thể tiếp tục vô hạn.

Dòng thứ hai in ra $N$ chuỗi.

Chuỗi thứ $i$ là kết quả của trạng thái khi quân cờ bắt đầu tại đỉnh $i$ và người đang đến lượt tại đỉnh đó thực hiện nước đi đầu tiên.

Các kết quả được in theo thứ tự:

$$1,2,\ldots,N.$$

Mỗi kết quả là một trong ba chuỗi:

WIN, LOSE, DRAW.

Các chuỗi trên cùng một dòng được phân cách bởi một dấu cách.

Subtask

Trong tất cả các Subtask: $1\le S\le N$ và mỗi cạnh $u\rightarrow v$ thỏa mãn $1\le u,v\le N$. Đồ thị có thể có chu trình.

• Subtask 1 — 40%: $1\le N\le20$; $0\le M\le60$;
• Subtask 2 — 60%: $1\le N\le2\cdot10^5$; $0\le M\le4\cdot10^5$;

2.0 s

Ví dụ

Ví dụ 1

Input

3 2 1
1 2
2 3

Output

LOSE
LOSE WIN LOSE

Giải thích

Đồ thị có dạng:

$$1\rightarrow2\rightarrow3.$$

Đỉnh $3$ không có cạnh đi ra.

Nếu một người chơi bắt đầu lượt của mình tại đỉnh $3$, người đó không thể thực hiện nước đi nào và thua ngay. Vì vậy:

$$3=\text{LOSE}.$$

Tại đỉnh $2$, người đang đến lượt có đúng một nước đi:

$$2\rightarrow3.$$

Sau nước đi này, đối thủ phải bắt đầu lượt tại đỉnh $3$, là một trạng thái LOSE.

Do đó người chơi tại đỉnh $2$ có thể buộc đối thủ thua:

$$2=\text{WIN}.$$

Tại đỉnh $1$, người chơi chỉ có thể đi:

$$1\rightarrow2.$$

Sau nước đi này, đối thủ bắt đầu lượt tại đỉnh $2$. Nhưng đỉnh $2$ là WIN đối với người đang đến lượt tại đó.

Vì không có lựa chọn nào khác nên người chơi bắt đầu tại đỉnh $1$ chắc chắn thua:

$$1=\text{LOSE}.$$

Do $S=1$, kết quả của trạng thái ban đầu là LOSE.

---

Ví dụ 2

Input

2 2 1
1 2
2 1

Output

DRAW
DRAW DRAW

Giải thích

Đồ thị tạo thành chu trình:

$$1\rightarrow2\rightarrow1.$$

Mỗi đỉnh đều có đúng một cạnh đi ra.

Nếu quân cờ bắt đầu ở đỉnh $1$, quá trình chơi bắt buộc diễn ra:

$$1\rightarrow2\rightarrow1\rightarrow2\rightarrow\cdots$$

Không có thời điểm nào quân cờ đến một đỉnh không còn nước đi.

Vì vậy không người chơi nào có thể buộc đối thủ thua. Ván đấu có thể tiếp tục vô hạn.

Do đó:

$$1=\text{DRAW}, \qquad 2=\text{DRAW}.$$

Vì $S=1$, kết quả ở dòng đầu tiên là DRAW.

---

Ví dụ 3

Input

4 4 1
1 2
1 3
2 4
3 3

Output

DRAW
DRAW WIN DRAW LOSE

Giải thích

Các cạnh của đồ thị là:

$$1\rightarrow2, \qquad 1\rightarrow3, \qquad 2\rightarrow4, \qquad 3\rightarrow3.$$

Đỉnh $4$ không có cạnh đi ra nên người bắt đầu lượt tại đây thua ngay:

$$4=\text{LOSE}.$$

Tại đỉnh $2$, người chơi có thể đi:

$$2\rightarrow4.$$

Đối thủ khi đó phải bắt đầu lượt tại đỉnh $4$ và thua. Vì vậy:

$$2=\text{WIN}.$$

Tại đỉnh $3$, chỉ có nước đi:

$$3\rightarrow3.$$

Mỗi lượt quân cờ lại quay về chính đỉnh $3$. Ván chơi có thể tiếp tục vô hạn, nên:

$$3=\text{DRAW}.$$

Cuối cùng, tại đỉnh $1$, người đang đến lượt có hai lựa chọn.

Nếu chọn:

$$1\rightarrow2,$$

đối thủ nhận trạng thái WIN, vì vậy lựa chọn này dẫn đến kết quả bất lợi.

Nếu chọn:

$$1\rightarrow3,$$

đối thủ nhận trạng thái DRAW, và ván chơi có thể tiếp tục vô hạn.

Người chơi tại đỉnh $1$ không thể buộc thắng, nhưng có thể tránh thua bằng cách chọn đỉnh $3$.

Vì vậy:

$$1=\text{DRAW}.$$

Do $S=1$, dòng đầu tiên là DRAW.