Tý cần thiết lập lộ trình giao hàng từ tổng kho \(S\) đến đại lý phân phối \(T\) trong mạng lưới logistics gồm \(N\) địa điểm trung chuyển và \(M\) tuyến đường nối trực tiếp hai chiều có thời gian di chuyển bằng nhau.

Hãy tìm lộ trình đi qua ít địa điểm trung chuyển nhất từ \(S\) đến \(T\). Nếu có nhiều lộ trình ngắn nhất cùng chiều dài, hãy in ra lộ trình có thứ tự từ điển nhỏ nhất của các địa điểm trung chuyển đi qua.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(0 \le M \le 2 \cdot 10^5\)).
• Dòng thứ hai chứa hai số nguyên \(S\) và \(T\).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả tuyến đường hai chiều giữa địa điểm \(u\) và \(v\).

Định dạng đầu ra

• Dòng đầu in ra số lượng địa điểm tối thiểu đi qua (bao gồm cả \(S\) và \(T\)), hoặc -1 nếu không có đường đi.
• Dòng thứ hai in ra chuỗi các địa điểm trên lộ trình ngắn nhất đó, cách nhau bởi dấu cách.

Ví dụ

Input:

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

Output:

3
1 2 4