Cho một đồ thị vô hướng, không trọng số gồm ~n~ đỉnh và ~m~ cạnh, các đỉnh được đánh số từ ~1~ đến ~n~. Hãy tìm một đường đi ngắn nhất (theo số cạnh) từ đỉnh ~s~ đến đỉnh ~t~. Nếu tồn tại, hãy truy vết và in ra một đường đi ngắn nhất đó.

Yêu cầu

• Xác định xem có đường đi từ ~s~ đến ~t~ hay không.
• Nếu có, in ra độ dài đường đi (số cạnh) và một đường đi cụ thể từ ~s~ tới ~t~ với thứ tự các đỉnh trên đường đi.
• Nếu không tồn tại đường đi, in -1.

Dữ liệu

• Dòng 1: Hai số nguyên ~n, m~ ~(1 \le n \le 2\cdot 10^5,\ 0 \le m \le 5\cdot 10^5)~.
• Dòng 2: Hai số nguyên ~s, t~ ~(1 \le s, t \le n)~.
• ~m~ dòng tiếp theo: mỗi dòng gồm hai số nguyên ~u, v~ ~(1 \le u, v \le n)~ biểu diễn một cạnh vô hướng giữa ~u~ và ~v~.

Ghi chú:

• Có thể có nhiều cạnh trùng lặp và/hoặc khuyên (cạnh ~u=u~); các trường hợp này không ảnh hưởng kết quả nếu bạn cài đặt đúng BFS.
• Đồ thị có thể không liên thông.

Kết quả

• Nếu không có đường đi: in một dòng duy nhất -1.
• Nếu có đường đi:
  • In một dòng chứa số nguyên ~d~: độ dài đường đi tính theo số cạnh (tức là số đỉnh trên đường đi trừ 1).
  • In dòng tiếp theo chứa ~d+1~ số nguyên: dãy các đỉnh trên một đường đi ngắn nhất từ ~s~ đến ~t~ (bắt đầu bằng ~s~, kết thúc bằng ~t~).

Ví dụ

Ví dụ 1

Input

6 7
1 5
1 2
2 3
3 5
2 4
4 6
6 5
1 3

Output

2
1 3 5

Giải thích
Một đường đi ngắn nhất từ 1 đến 5 là ~1 \to 3 \to 5~ với 2 cạnh.

Ví dụ 2

Input

4 1
2 4
1 2

Output

-1

Giải thích
Không có đường đi từ 2 đến 4.

Ví dụ 3 (trường hợp ~s = t~)

Input

5 3
4 4
1 2
2 3
3 5

Output

0
4

Giải thích

Đường đi ngắn nhất có độ dài 0 cạnh, chỉ gồm đỉnh 4.

Subtasks

• Subtask 1 (20%): ~1 \le n \le 2000,\ 0 \le m \le 5000~.
• Subtask 2 (30%): Đồ thị là cây (~m = n-1~).
• Subtask 3 (50%): Ràng buộc tổng quát như đề.

Yêu cầu chấm điểm

• Đường đi in ra phải hợp lệ (liền kề theo cạnh) và có độ dài tối ưu.
• Chấp nhận bất kỳ đường đi ngắn nhất nào (nếu có nhiều đường đi tối ưu).