Có ~N~ tỉnh thành. An đi du lịch từ tỉnh ~P~ đến tỉnh ~Q~. Biết rằng đường đi giữa ~2~ tỉnh thành là bất kỳ (nếu có) đều là đường đi hai chiều. Sơ đồ mạng lưới giao thông của ~N~ tỉnh thành này cho bởi bảng vuông ~N \times N~ giá trị (ma trận) đối xứng ~A[i,j]~, trong đó ~A[i,j] \geq 0~, ~A[i,j]~ là số nguyên và có thể có các giá trị sau:

• ~A[i,j]>0~ là độ dài đường đi từ tỉnh ~i~ đến tỉnh ~j~.
• ~A[i,j] = 0~ nếu không có đường đi từ tỉnh ~i~ đến tỉnh ~j~.
• ~A[i,j] = A[j,i]~.

Yêu cầu:

Tìm đường đi ngắn nhất từ tỉnh ~P~ đến tỉnh ~Q~.

Dữ liệu vào

• Dòng đầu là số ~N~ ( ~N~ nguyên dương, ~N \leq 50~).
• Dòng ~i+1~ ~( 1 \leq i \leq N )~ ghi ~N~ số nguyên dương ~A[i,1], A[i,2] .....A[i,N]~.
• Dòng ~N+2~ ghi ~2~ số ~P~ và ~Q~.

Kết quả ra

• Dòng thứ nhất: Độ dài của đường đi ngắn nhất từ ~P~ đến ~Q~, ngược lại không có đường đi ghi ~-1~.
• Dòng dòng thứ hai: Các tỉnh đã đi qua (nếu có), kể cả ~P, Q~.

Sample Input 1

6
0  5  0  0  0  9
5  0  6  0  0  0
0  6  0  7  0  0
0  0  7  0  8  0
0  0  0  8  0  9
9  0  0  0  9  0
1  5

Sample Output 1

18
1 6  5

Sample Input 2

4
0  2  3  0
2  0  5  0
3  5  0  0
0  0  0  0
2  4

Sample Output 2

-1