Đây là một bài toán chỉ yêu cầu xuất dữ liệu (output-only). Lưu ý rằng bạn vẫn phải gửi mã nguồn in ra kết quả, thay vì gửi một tệp văn bản.

Một cách tô 3 màu hợp lệ của một đồ thị là việc gán các màu (số) từ tập $\{1, 2, 3\}$ cho mỗi đỉnh sao cho với mọi cạnh $(a, b)$ của đồ thị, hai đỉnh $a$ và $b$ có màu khác nhau. Có tối đa $3^n$ cách tô màu như vậy cho một đồ thị có $n$ đỉnh.

Bạn làm việc trong một công ty, với mục tiêu trở thành chuyên gia trong việc tạo ra các đồ thị có số lượng cách tô 3 màu cho trước. Một ngày nọ, bạn biết rằng vào buổi tối bạn sẽ nhận được đơn hàng tạo ra một đồ thị có đúng $6k$ cách tô 3 màu. Bạn không biết giá trị chính xác của $k$, chỉ biết rằng $1 \le k \le 500$.

Bạn không muốn đợi đến khi biết giá trị cụ thể của $k$ mới bắt đầu tạo đồ thị. Do đó, bạn xây dựng trước một đồ thị với tối đa 19 đỉnh. Sau đó, khi đã biết giá trị $k$ cụ thể, bạn được phép thêm tối đa 17 cạnh vào đồ thị để thu được đồ thị yêu cầu với đúng $6k$ cách tô 3 màu.

Bạn có làm được không?

Dữ liệu vào

Không có dữ liệu vào cho bài toán này.

Dữ liệu ra

Đầu tiên, xuất $n$ và $m$ ($1 \le n \le 19$, $1 \le m \le \frac{n(n-1)}{2}$) — số lượng đỉnh và số lượng cạnh của đồ thị ban đầu (đồ thị được xây dựng trước). Sau đó, xuất $m$ dòng có dạng $(u, v)$ — các cạnh của đồ thị.

Tiếp theo, với mỗi $k$ từ 1 đến 500, thực hiện các bước sau:

Xuất $e$ — số lượng cạnh bạn sẽ thêm vào cho giá trị $k$ cụ thể này ($1 \le e \le 17$). Sau đó, xuất $e$ dòng có dạng $(u, v)$ — các cạnh bạn sẽ thêm vào đồ thị của mình.

Đồ thị không được có khuyên (self-loop), và với mỗi $k$, tất cả $m + e$ cạnh bạn sử dụng phải đôi một khác nhau. Số lượng cách tô 3 màu của đồ thị với một giá trị $k$ cụ thể phải đúng bằng $6k$.

Ví dụ

Ví dụ 1

3 2
1 2
2 3
1
1 3
0

Ghi chú

Kết quả mẫu được đưa ra như một ví dụ. Nó chứa kết quả cho $k = 1, 2$.