Khu vực SAN ANDREAS có \(N\) ngôi nhà và \(M\) đường giao thông một chiều. Mỗi con đường kết nối trực tiếp giữa 2 ngôi nhà. Các ngôi nhà được đánh số từ \(1\) tới \(N\). CJ đang chuẩn bị thanh toán nhóm BALLAS ở một ngôi nhà trong khu vực, và sẽ bắt đầu tại nhà của CJ. Nhà của CJ có chỉ số là \(s\), nhà của nhóm BALLAS có chỉ số là \(t\). Một đường đi gọi là đường đi đơn nếu trong quá trình đi từ nhà CJ tới nhà của nhóm BALLAS, tất cả ngôi nhà đi qua nhiều nhất một lần. Và tồn tại ít nhất một đường đi từ \(s\) tới \(t\) (vì thế CJ mới có thể đi thanh toán được).

Hãy tìm cho CJ đường đi đơn ngắn nhất để CJ nhanh chóng thanh toán nhóm BALLAS càng nhanh càng tốt (CJ còn nhiều việc chưa giải quyết xong). Nếu có nhiều đường đi đơn ngắn nhất, thì chỉ ra đường đi có thứ tự từ điển nhỏ nhất trong số đó.

Input

• Dòng đầu tiên chứa 4 số nguyên dương \(N,M,s,t \ (1 \leq s, t \leq N, s \ne t)\).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v \ (1 \leq u, v \leq N, u \ne v)\) thể hiện có đường đi một chiều nối từ ngôi nhà \(u\) tới ngôi nhà \(v\) trong khu vực.

Output

• Ghi ra trên một dòng các ngôi nhà theo đúng thứ tự trên đường đi ngắn nhất tìm được, bắt đầu từ ngôi nhà \(s\), kết thúc ở ngôi nhà \(t\) theo thứ tự từ điển nhỏ nhất (Ví dụ \(10\) có thứ tự từ điển lớn hơn \(5\), \(5\) có thứ tự từ điển lớn hơn \(1\)).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3, M \leq 10^4\).
• Subtask \(2\) (\(70\%\) số điểm): \(N \leq 10^5, M \leq 10^6\).

Example

8 12 1 8
1 3
3 5
7 6
1 2
2 4
2 3
3 1
3 7
6 8
4 6
6 2
7 8 

1 3 7 8