Special Graph Construction

All submissions for this problem are available.
If you are not familiar with graph theory terminology, please visit the end of the problem to see definitions. You 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:  It has $\le 10^5$ vertices.  It is a simple, undirected, connected 3regular graph.  It has exactly $k$ bridge edges, ($k$ given as input). For 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't like graphs with a high value of $f$, so he asks you to minimize it. If there doesn't 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. ### Input  The only line of the input contains a single integer $k$, the required number of bridge edges. ### Output If 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.  In the first line, print $n$ and $m$.  In $i^{\text{th}}$ of the next $m$ lines, print the edge numbered $i$ as its endpoints separated by a space.  In the last line, print $f(G)$ followed by the indices of the edges in $X$. You can print the indices in any order. For example if $f(G) = 4$, and removing edges with indices $\{2, 4, 5, 7\}$ makes the graph bipartite, you can print `4 5 2 7 4`. Your 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. ### Constraints  $0 \le k \le 10^4$ ### Example Input ``` 0 ``` ### Example Output ``` 6 9 1 4 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6 0 ``` ### Explanation The 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. If you already know the graph theory terms used in the statement, you can skip reading the following definitions: **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. **Simple graph**  A graph $G$ is called simple if there are no selfloops (edge from a node to itself) or multiple edges( more than one edge between a pair of vertices). **3regular graph**  A 3regular graph is one in which every vertex is an endpoint of exactly $3$ edges. **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$. **Bridge edge**  An edge is called a bridge edge if on removing it, the graph is no longer connected.Author:  jtnydv25 
Tags  jtnydv25 
Date Added:  25112019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 