{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"If you are not familiar with graph theory terminology, please visit the end of the problem to see definitions.\r\n\r\nYou are in the graph construction business. A client of yours has asked for a special graph. A graph is called special if it satisfies the following properties:\r\n- It has $\\le 10^5$ vertices.\r\n- It is a simple, undirected, connected 3-regular graph.\r\n- It has exactly $k$ bridge edges, ($k$ given as input).\r\n\r\nFor a graph $G$, define $f(G)$ to be the minimum number of edges to be removed from it to make it bipartite. The client doesn\u0027t like graphs with a high value of $f$, so he asks you to minimize it.\r\n\r\nIf there doesn\u0027t exist any special graph, print $-1$. Otherwise, find a special graph $G$ with the minimum possible value of $f(G)$ and also find a subset of its edges of size $f(G)$ whose removal makes it bipartite . In case there are multiple such graphs, you can output any of those.\r\n\r\n### Input\r\n- The only line of the input contains a single integer $k$, the required number of bridge edges.\r\n\r\n### Output\r\nIf there are no special graphs, print a single line containing the integer $-1$. Otherwise, let $G$ be your graph with $n$ vertices numbered $1, 2, \\ldots n$ and $m$ edges numbered $1, 2, \\ldots m$. Let $X$ be a subset of edges of size $f(G)$ whose removal makes the graph bipartite. If there are multiple choices for $X$, you can choose any one of them.\r\n\r\n- In the first line, print $n$ and $m$.\r\n- In $i^{\\text{th}}$ of the next $m$ lines, print the edge numbered $i$ as its endpoints separated by a space.\r\n- In the last line, print $f(G)$ followed by the indices of the edges in $X$. You can print the indices in any order.\r\n\r\nFor example if $f(G) \u003d 4$, and removing edges with indices $\\{2, 4, 5, 7\\}$ makes the graph bipartite, you can print `4 5 2 7 4`.\r\n\r\nYour answer is considered correct if and only if it is a special graph and of all the special graphs, it has the minimum possible $f$ value, and removing edges in $X$, the remaining graph is bipartite.\r\n\r\n### Constraints \r\n- $0 \\le k \\le 10^4$\r\n\r\n### Example Input\r\n```\r\n0\r\n```\r\n\r\n### Example Output\r\n```\r\n6 9\r\n1 4\r\n1 5\r\n1 6\r\n2 4\r\n2 5\r\n2 6\r\n3 4\r\n3 5\r\n3 6\r\n0\r\n```\r\n\r\n### Explanation\r\nThe graph printed is a bipartite graph with 3 nodes on both sides. Each node is connected to every node on the opposite side. Every node has a degree $3$; there is no bridge edge. Since it is a bipartite graph, it has a $f$ value of $0$, which is the minimum possible.\r\n\r\nIf you already know the graph theory terms used in the statement, you can skip reading the \r\nfollowing definitions:\r\n\r\n**Connected graph** - A graph is said to be connected if, for every two nodes, you can reach one from the other using the edges of the graph.\r\n\r\n**Simple graph** - A graph $G$ is called simple if there are no self-loops (edge from a node to itself) or multiple edges( more than one edge between a pair of vertices).\r\n\r\n**3-regular graph** - A 3-regular graph is one in which every vertex is an endpoint of exactly $3$ edges.\r\n\r\n**Bipartite graph** - A bipartite graph is a graph whose vertices can be divided into two disjoint sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$.\r\n\r\n**Bridge edge** - An edge is called a bridge edge if on removing it, the graph is no longer connected."}}]}