Đường đi đơn có thứ tự từ điển nhỏ nhất

Cho một đồ thị có hướng \(G=(V, E)\) gồm \(N\) đỉnh và \(M\) cung. Hai đỉnh \(s\) và \(t\) được cho trước. Một đường đi đơn là một dãy các đỉnh \(P=\langle p_0, p_1, \dots, p_k \rangle\) sao cho \(p_0=s\), \(p_k=t\), \((p_{i-1}, p_i) \in E\), và tất cả các đỉnh trên đường đi đều đôi một khác nhau.

Yêu cầu: Biết rằng tồn tại ít nhất một đường đi từ \(s\) tới \(t\), hãy tìm và chỉ ra đường đi đơn từ \(s\) đến \(t\) có thứ tự từ điển nhỏ nhất. Nếu không tồn tại đường đi, in ra -1.

Một đường đi \(P\) được coi là nhỏ hơn về thứ tự từ điển so với đường đi \(Q\) nếu tại chỉ số đầu tiên mà các đỉnh tương ứng khác nhau, đỉnh của \(P\) có chỉ số nhỏ hơn.

Input

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

Output

Ghi ra trên một dòng các đỉnh theo đúng thứ tự trên đường đi đơn giản có thứ tự từ điển nhỏ nhất tìm được, bắt đầu từ đỉnh \(s\) và kết thúc ở đỉnh \(t\), cách nhau một dấu cách. Nếu không tồn tại đường đi, in ra -1.

Example

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

1 2 3 7 5 8