Cho đồ thị có hướng \(G=(V,E)\) gồm \(N\) đỉnh và \(M\) cung, \(s\) và \(t\) là hai đỉnh của đồ thị \(G\). Một dãy các đỉnh \(P=\langle p_0=s, p_1, p_2, \dots, p_k=t \rangle\) sao cho \((p_{i_1}, p_i) \in E\), được gọi là 1 đường đi từ \(s\) đến \(t\). Một đường đi đơn giản (còn gọi là đường đi đơn) nếu tất cả các đỉnh trên đường đi đôi một khác nhau.
Biết rằng tồn tại ít nhất một đường đi từ s tới t, hãy chỉ ra đường đi đơn có thứ tự từ điển nhỏ nhất.

Input

• Dòng đầu chứa các số nguyên \(N\), \(M\), đỉnh xuất phát \(s\), đỉnh cần đến \(t\).
• \(M\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(u,v\) \((1 \leq u,v \leq N)\), thể hiện cho 1 cung nối từ đỉnh \(u\) đến đỉnh $v trong đồ thị.

Output

• Ghi ra trên một dòng các đỉnh theo đúng thứ tự trên đường đi tìm được, bắt đầu từ đỉnh \(s\), kết thúc ở đỉnh \(t\) theo thứ tự từ điển nhỏ nhất.

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 2
1 3
2 3
2 4
3 1
3 5
3 7
4 6
6 2
6 8
7 8
7 6 

1 2 3 7 6 8