Cho một đồ thị có hướng \(G = (V, E)\) gồm \(N\) đỉnh và \(M\) cạnh.
Một đường đi từ đỉnh \(s\) đến đỉnh \(t\) là một dãy các đỉnh
\(P = \{P_1, P_2, \ldots, P_x\}\) khác nhau sao cho \((P_{i-1}, P_i) \in E\).

Yêu cầu: Cho hai đỉnh \(s\) và \(t\). Hãy tìm đường đi có thứ tự từ điển ngắn nhất từ \(s\) đến \(t\).

Input

• Dòng đầu tiên chứa 4 số nguyên dương \(n, m, s, t\)
  \((n \le 10^5, m \le 10^6; 1 \le s, t \le n)\).
• \(m\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(u, v\),
  mô tả cạnh đi từ \(u\) đến \(v\) \((1 \le u, v \le n)\).

Output

• In ra dãy số nguyên là đường đi có thứ tự từ điển nhỏ nhất từ \(s\) đến \(t\).
• Dữ liệu đảm bảo luôn tồn tại đường đi thoả mãn.

Example

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

1 2 3 4