Hòn đảo cô đơn

Trong một buổi học về lập trình, FullHouse Dev được giao một bài toán thú vị về các hòn đảo. Họ cần phải tính toán xác suất để tìm ra hòn đảo mà người chơi có khả năng kẹt lại cao nhất. Với tinh thần nhiệt huyết, nhóm đã bắt tay vào giải quyết thử thách này.

Bài toán

Có nhiều hòn đảo được kết nối bởi các cầu một chiều. Nếu một cầu nối từ đảo \(i\) đến đảo \(j\), bạn chỉ có thể di chuyển từ \(i\) đến \(j\) mà không thể quay lại. Khi ở trên đảo \(i\), bạn sẽ ngẫu nhiên chọn một trong các đảo có thể đi đến trực tiếp từ \(i\) thông qua cầu một chiều. Bạn sẽ bị kẹt trên một đảo nếu không thể di chuyển tiếp. Đảm bảo rằng sau khi rời khỏi một đảo, bạn không thể quay lại đảo đó.

Hãy tìm hòn đảo mà bạn có khả năng bị kẹt cao nhất. Hai đảo được coi là có xác suất bằng nhau nếu chênh lệch tuyệt đối của xác suất kẹt lại trên chúng là \(10^{-6}\).

INPUT FORMAT:

• Dòng đầu tiên chứa ba số nguyên \(n\) (số lượng đảo), \(m\) (số lượng cầu một chiều), và \(s\) (chỉ số của đảo xuất phát)
• \(m\) dòng tiếp theo: Mỗi dòng chứa hai số nguyên \(u\) và \(v\) biểu thị một cầu một chiều từ đảo \(u\) đến đảo \(v\)

OUTPUT FORMAT:

• In ra chỉ số của đảo mà bạn có khả năng bị kẹt cao nhất. Nếu có nhiều đảo, hãy in ra các chỉ số theo thứ tự tăng dần (các giá trị cách nhau bởi dấu cách trên một dòng).

Ràng buộc:

• \(1 \leq n \leq 100\)
• \(1 \leq m \leq n(n-1)\)
• \(1 \leq s \leq n\)
• \(1 \leq u, v \leq n\)

Ví dụ

INPUT

5 7 1
1 2
1 3
1 4
1 5
2 4
2 5
3 4

OUTPUT

4

Giải thích

Có hai đảo mà bạn có thể bị kẹt - đảo 4 và đảo 5, trong đó đảo 4 có xác suất cao hơn.