Bạn được cho một đồ thị vô hướng đơn không có khuyên hay đa cạnh. Một số cạnh được đánh dấu là Special (đặc biệt).

Nhiệm vụ của bạn là tìm một chu trình đơn sao cho với mỗi cạnh Special, cạnh đó hoặc thuộc về chu trình, hoặc không có đỉnh đầu mút nào của nó nằm trên chu trình. Chu trình không được phép lặp lại các đỉnh. Hãy xuất ra bất kỳ lời giải nào, hoặc thông báo nếu không tồn tại.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa ba số nguyên $n$ ($2 \le n \le 150$), $m$ ($1 \le m \le \frac{n(n-1)}{2}$) và $k$ ($1 \le k \le m$), trong đó $n$ là số lượng đỉnh trong đồ thị, $m$ là số lượng cạnh và $k$ là số lượng cạnh Special. Các đỉnh được đánh số từ $1$ đến $n$.

Mỗi dòng trong $m$ dòng tiếp theo chứa hai số nguyên $a$ và $b$ ($1 \le a < b \le n$), biểu thị một cạnh vô hướng giữa đỉnh $a$ và đỉnh $b$. Tất cả các cạnh là phân biệt. $k$ cạnh đầu tiên là các cạnh Special.

Dữ liệu ra

Xuất ra một số nguyên biểu thị độ dài của chu trình tìm được trên một dòng. Trên các dòng tiếp theo, xuất ra các đỉnh của chu trình theo thứ tự dọc theo chu trình, mỗi đỉnh trên một dòng. Nếu không tồn tại chu trình như vậy, chỉ cần xuất ra $-1$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

8
1
4
5
6
7
8
3
2

Dữ liệu vào 2

4 6 3
1 2
1 3
1 4
2 3
3 4
2 4

Dữ liệu ra 2

-1