Đường đi ngắn nhất nhỏ nhất

Cho một đồ thị vô hướng gồm $n$ đỉnh đánh số từ $1$ đến $n$ và $m$ cạnh. Đồ thị có thể có khuyên và nhiều cạnh nối cùng một cặp đỉnh.

Trong tất cả các đường đi từ đỉnh $1$ tới đỉnh $n$ đi qua ít cạnh nhất, hãy tìm đường đi có dãy đỉnh nhỏ nhất theo thứ tự từ điển.

Dãy đỉnh $a_0,a_1,\dots ,a_d$ nhỏ hơn dãy $b_0,b_1,\dots ,b_d$ (cùng độ dài) theo thứ tự từ điển nếu tại vị trí $i$ đầu tiên mà hai dãy khác nhau, ta có $a_i<b_i$.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ cho biết có một cạnh nối $u$ và $v$.

Dữ liệu ra

• Nếu không có đường đi từ $1$ tới $n$, in ra một số $-1$.
• Ngược lại, dòng thứ nhất in ra $d$ là số cạnh trên đường đi ngắn nhất. Dòng thứ hai in ra $d+1$ đỉnh của đường đi cần tìm, bắt đầu bằng $1$ và kết thúc bằng $n$, cách nhau bởi một dấu cách.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $0\le m\le 2·{10}^5$
• $1\le u,v\le n$

Ví dụ