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 ở phòng $1$ và cần đến phòng $n$ bằng cách đi qua các máy dịch chuyển. Mỗi máy dịch chuyển chỉ được dùng nhiều nhất một lần trong toàn bộ $k$ ngày, và mỗi lần dùng tốn một đồng xu.

Hãy tìm số đồng xu ít nhất để hoàn thành đủ $k$ ngày, đồng thời in ra lộ trình của từng ngày.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$ là số phòng, số máy dịch chuyển và số ngày.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ mô tả một máy dịch chuyển đi từ phòng $a$ sang phòng $b$. Máy dịch chuyển chỉ đi được một chiều.

Dữ liệu ra

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

Ngược lại, dòng đầu in số đồng xu ít nhất. Sau đó với mỗi ngày in hai dòng: dòng thứ nhất là số phòng trên lộ trình của ngày đó (tính cả phòng $1$ và phòng $n$), dòng thứ hai là danh sách các phòng theo đúng thứ tự đi qua.

Nếu có nhiều phương án cùng đạt số đồng xu ít nhất, in ra một phương án bất kỳ; thứ tự các ngày cũng tuỳ ý.

Ràng buộc

• $2\le n\le 500$
• $1\le m\le 1000$
• $1\le k\le n-1$
• Không có hai máy dịch chuyển nào cùng đi từ một phòng sang cùng một phòng

Ví dụ