Một trò chơi bao gồm \(n\) phòng và \(m\) cổng dịch chuyển tức thời. Vào đầu mỗi ngày, bạn bắt đầu ở phòng \(1\) và bạn phải đến phòng \(n\).

Bạn có thể sử dụng tối đa mỗi cổng dịch chuyển tức thời một lần trong trò chơi. Bạn muốn chơi trò chơi trong chính xác \(k\) ngày. Mỗi khi bạn sử dụng bất kỳ cổng dịch chuyển tức thời nào, bạn phải trả một đồng xu. Số đồng xu tối thiểu bạn phải trả trong \(k\) ngày nếu bạn chơi tối ưu là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có ba số nguyên \(n\), \(m\) và \(k\): số lượng phòng, số lượng cổng dịch chuyển tức thời và số ngày bạn chơi trò chơi. Các phòng được đánh số \(1, 2, \ldots, n\).
• Sau này, có \(m\) dòng mô tả các cổng dịch chuyển tức thời. Mỗi dòng có hai số nguyên \(a\) và \(b\): có một cổng dịch chuyển tức thời từ phòng \(a\) đến phòng \(b\).
• Không có hai cổng dịch chuyển tức thời có phòng bắt đầu và kết thúc giống nhau.

Output

• Đầu tiên in một số nguyên: số đồng xu tối thiểu bạn phải trả nếu bạn chơi tối ưu. Sau đó, in \(k\) mô tả lộ trình theo ví dụ. Bạn có thể in bất kỳ giải pháp hợp lệ nào.
• Nếu không thể chơi trò chơi trong \(k\) ngày, chỉ in \(-1\).

Constraints

• \(2 \leq n \leq 500\)
• \(1 \leq m \leq 1000\)
• \(1 \leq k \leq n - 1\)
• \(1 \leq a, b \leq n\)

Example

8 10 2
1 2
1 3
2 5
2 4
3 5
3 6
4 8
5 8
6 7
7 8

6
4
1 2 4 8
4
1 3 5 8