Graph Construction for Exact Three-Colorings

A valid three‐coloring of a graph is an assignment of colors from the set \(\{1,2,3\}\) to every vertex so that any two adjacent vertices receive different colors. It is well known that for a graph on \(n\) vertices, the maximum number of valid three‐colorings is \(3^n\).

In this problem, you are given an initially constructed undirected graph with \(n\) vertices and \(m\) edges, where \(1 \le n \le 19\) and \(1 \le m \le \frac{n(n-1)}{2}\). Furthermore, for every integer \(k\) with \(1 \le k \le 500\), you are allowed to add at most 17 additional undirected edges (without adding duplicate edges or self-loops) to the graph so that the total number of valid three-colorings becomes exactly \(6k\) (i.e. a multiple of 6).

This is an output-only problem.

inputFormat

There is no input for this problem.

outputFormat

Output the constructed graph in the following format:

1. The first line contains two integers \(n\) and \(m\), representing the number of vertices and the number of edges in the initial graph, respectively.
2. The following \(m\) lines each contain two integers \(u\) and \(v\) (with 1-based indexing) which denote an undirected edge between vertices \(u\) and \(v\).

Your constructed graph must satisfy the requirements mentioned above. (Note: Since this is an output-only problem, your program does not need to read any input.)

sample

3 3
1 2
2 3
3 1