1178D.md (2584B)
1 Source: https://codeforces.com/problemset/problem/1178/D 2 3 D. Prime Graph 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Every person likes prime numbers. Alice is a person, thus she also shares the love for them. Bob wanted to give her an affectionate gift but couldn't think of anything inventive. Hence, he will be giving her a graph. How original, Bob! Alice will surely be thrilled! 22 23 When building the graph, he needs four conditions to be satisfied: 24 25 * It must be a simple undirected graph, i.e. without multiple (parallel) edges and self-loops. 26 * The number of vertices must be exactly $n$ — a number he selected. This number is not necessarily prime. 27 * The total number of edges must be prime. 28 * The degree (i.e. the number of edges connected to the vertex) of each vertex must be prime. 29 30 Below is an example for $n = 4$. The first graph (left one) is invalid as the degree of vertex $2$ (and $4$) equals to $1$, which is not prime. The second graph (middle one) is invalid as the total number of edges is $4$, which is not a prime number. The third graph (right one) is a valid answer for $n = 4$. 31 32  33 34 Note that the graph can be disconnected. 35 36 Please help Bob to find any such graph! 37 38 Input 39 40 The input consists of a single integer $n$ ($3 \leq n \leq 1\,000$) — the number of vertices. 41 42 Output 43 44 If there is no graph satisfying the conditions, print a single line containing the integer $-1$. 45 46 Otherwise, first print a line containing a prime number $m$ ($2 \leq m \leq \frac{n(n-1)}{2}$) — the number of edges in the graph. Then, print $m$ lines, the $i$-th of which containing two integers $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n$) — meaning that there is an edge between vertices $u_i$ and $v_i$. The degree of each vertex must be prime. There must be no multiple (parallel) edges or self-loops. 47 48 If there are multiple solutions, you may print any of them. 49 50 Note that the graph can be disconnected. 51 52 Examples 53 54 Input 55 56 ``` 57 4 58 ``` 59 60 Output 61 62 ``` 63 5 64 1 2 65 1 3 66 2 3 67 2 4 68 3 4 69 ``` 70 71 Input 72 73 ``` 74 8 75 ``` 76 77 Output 78 79 ``` 80 13 81 1 2 82 1 3 83 2 3 84 1 4 85 2 4 86 1 5 87 2 5 88 1 6 89 2 6 90 1 7 91 1 8 92 5 8 93 7 8 94 ``` 95 96 Note 97 98 The first example was described in the statement. 99 100 In the second example, the degrees of vertices are $[7, 5, 2, 2, 3, 2, 2, 3]$. Each of these numbers is prime. Additionally, the number of edges, $13$, is also a prime number, hence both conditions are satisfied. 101 102 