Tập đoàn Bumbershoot độc ác sản xuất người vô tính để phục vụ những thí nghiệm rùng rợn trong một phòng thí nghiệm ngầm rộng lớn. Trong một lần, tập đoàn đã nhân bản cậu bé Per — người thông minh hơn hẳn các bản sao khác. Per lập tức nhận ra có điều mờ ám, liền tập hợp các bản sao cùng nổi dậy chống lại tập đoàn và đi tìm lối thoát khỏi phòng thí nghiệm. Tập đoàn quyết định cho nổ tung toàn bộ khu phức hợp.

Phòng thí nghiệm được mô tả bằng một đồ thị liên thông gồm ~n~ đỉnh và ~m~ cạnh. Có ~k~ bản sao của Per bắt đầu tìm lối thoát từ một số đỉnh nào đó. Mỗi bản sao đi qua một cạnh mất một giây. Nhiều bản sao được phép đứng ở cùng một đỉnh cùng lúc. Mỗi bản sao có thể dừng tìm kiếm bất cứ lúc nào, nhưng ít nhất phải thăm đỉnh xuất phát của mình. Lối thoát có thể nằm ở bất kỳ đỉnh nào, vì vậy mỗi đỉnh phải được ít nhất một bản sao ghé thăm.

Mỗi bản sao chỉ kịp thăm nhiều nhất ~\left\lceil \frac{2n}{k} \right\rceil~ đỉnh trước khi phòng thí nghiệm phát nổ.

Nhiệm vụ của bạn là chọn đỉnh xuất phát và lộ trình tìm kiếm cho từng bản sao. Mỗi lộ trình có nhiều nhất ~\left\lceil \frac{2n}{k} \right\rceil~ đỉnh.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên ~n~, ~m~ và ~k~ — số đỉnh, số cạnh của phòng thí nghiệm và số bản sao.
• Mỗi dòng trong ~m~ dòng tiếp theo chứa hai số nguyên ~x_i~ và ~y_i~ — chỉ số hai đỉnh được nối bởi cạnh tương ứng. Đồ thị có thể chứa khuyên và cạnh bội.

Đồ thị được đảm bảo liên thông.

Kết quả

In ra ~k~ dòng. Dòng thứ ~i~ bắt đầu bằng số nguyên ~c_i~ (~1 \le c_i \le \left\lceil \frac{2n}{k} \right\rceil~) — số đỉnh mà bản sao thứ ~i~ ghé thăm, theo sau là ~c_i~ số nguyên — chỉ số các đỉnh theo thứ tự ghé thăm. Bạn phải in một đỉnh mỗi lần nó được ghé thăm, kể cả khi nó đã được thăm trước đó.

Nếu có nhiều đáp án hợp lệ, in ra một đáp án bất kỳ. Dữ liệu đảm bảo luôn tồn tại đáp án.

Ví dụ

Đầu vào:

3 2 1
2 1
3 1

Đầu ra:

3 2 1 3

Đầu vào:

5 4 2
1 2
1 3
1 4
1 5

Đầu ra:

3 2 1 3
3 4 1 5

Giải thích: Ở ví dụ thứ nhất chỉ có một bản sao, đi theo thứ tự ~(2, 1, 3)~, thỏa mãn giới hạn ~6~ đỉnh mỗi bản sao. Ở ví dụ thứ hai, hai bản sao đi theo thứ tự ~(2, 1, 3)~ và ~(4, 1, 5)~, thỏa mãn giới hạn ~5~ đỉnh mỗi bản sao.

Giới hạn

• ~1 \le n \le 2 \cdot 10^5~
• ~n - 1 \le m \le 2 \cdot 10^5~
• ~1 \le k \le n~
• ~1 \le x_i, y_i \le n~