Hòn đảo cô đơn

Trong một chuyến du lịch khám phá các hòn đảo, FullHouse Dev đã tình cờ gặp một bài toán thú vị về các cây cầu một chiều. Với tinh thần khám phá, nhóm quyết định giải quyết bài toán này để tìm ra hòn đảo cuối cùng mà họ sẽ dừng chân.

Bài toán

Có nhiều hòn đảo được kết nối bởi các cây cầu một chiều. Nếu một cây cầu nối từ đảo \(i\) đến đảo \(j\), bạn chỉ có thể di chuyển từ đảo \(i\) sang đảo \(j\) mà không thể quay lại. Khi đứng ở đả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ừ đảo \(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 cao nhất sẽ bị kẹt lại. 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ây 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 cao nhất sẽ bị kẹt lại. Nếu có nhiều đảo thỏa mãn, in ra các chỉ số theo thứ tự tăng dần (các số 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\)

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 lại - đảo 4 và đảo 5, trong đó đảo 4 có xác suất cao hơn.