Lộ Trình Khác Biệt II

Bạn chơi một trò chơi trong $k$ ngày. Mỗi ngày, bạn bắt đầu tại phòng $1$ và cần đến phòng $n$, di chuyển qua các máy dịch chuyển. Mỗi máy dịch chuyển chỉ có thể được sử dụng tối đa một lần trong toàn bộ $k$ ngày. Sử dụng một máy dịch chuyển tốn một đồng xu.

Tìm số đồng xu tối thiểu để hoàn thành đủ $k$ ngày, đồng thời in ra lộ trình của mỗi ngày.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $n$, $m$, $k$ — số phòng, số máy dịch chuyển, và số ngày cần hoàn thành.

• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ — mô tả máy dịch chuyển từ phòng $a$ đến phòng $b$.

Dữ liệu ra

Nếu không thể hoàn thành $k$ ngày, in $-1$.

Ngược lại, dòng đầu tiên in số đồng xu tối thiểu. Tiếp theo, với mỗi ngày, in số phòng trên lộ trình (bao gồm phòng $1$ và phòng $n$) trên một dòng, và in các phòng trên dòng tiếp theo.

Ràng buộc

• $2\le n\le 500$
• $1\le m\le 1000$
• $1\le k\le n-1$
• Không có máy dịch chuyển trùng lặp giữa cùng hai phòng

Ví dụ