Codeforces Global Round 4 Prime Graph CodeForces

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!

When building the graph, he needs four conditions to be satisfied:

It must be a simple undirected graph, i.e. without multiple (parallel) edges and self-loops.

The number of vertices must be exactly n — a number he selected. This number is not necessarily prime.

The total number of edges must be prime.

The degree (i.e. the number of edges connected to the vertex) of each vertex must be prime.

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.

Note that the graph can be disconnected.

Please help Bob to find any such graph!

Input

The input consists of a single integer n (3≤n≤1000) — the number of vertices.

Output

If there is no graph satisfying the conditions, print a single line containing the integer −1.

Otherwise, first print a line containing a prime number m (2≤m≤n(n−1)2) — the number of edges in the graph. Then, print m lines, the i-th of which containing two integers ui, vi (1≤ui,vi≤n) — meaning that there is an edge between vertices ui and vi. The degree of each vertex must be prime. There must be no multiple (parallel) edges or self-loops.

If there are multiple solutions, you may print any of them.

Note that the graph can be disconnected.

Examples

Input

4

Output

5

1 2

1 3

2 3

2 4

3 4

Input

8

Output

13

1 2

1 3

2 3

1 4

2 4

1 5

2 5

1 6

2 6

1 7

1 8

5 8

7 8

Note

The first example was described in the statement.

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.

题意：

让你构造一个n个接点的图，使其边的总个数是质数，每一个节点的度数也是质数。

思路：

利用一个性质 n~n+n/2 这个区间里，必定有一个数是质数。

那么我们可以先把图连成一个圆环，现在边的个数是n。

如果当前边的个数不是质数，那么从1开始，在圆环中加入1与它在圆环中的对面节点1+n/2 连接而成的边。

还不是质数就加入2与对面节点的边，这样可以最多加到 n+n/2个边，根据上面的性质我们可以知道，这个过程中必有边数sum是质数的。

有因为这个过程中每一个节点的度数是2或者3. 所以整体是满足条件的。

细节见代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#include <iomanip>

#define ALL(x) (x).begin(), (x).end()

#define rt return

#define dll(x) scanf("%I64d",&x)

#define xll(x) printf("%I64d\n",x)

#define sz(a) int(a.size())

#define all(a) a.begin(), a.end()

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define gg(x) getInt(&x)

#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}

ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}

inline void getInt(int* p);

const int maxn = 1000010;

const int inf = 0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

// const int maxn = 1e7+50;

bool noprime[maxn + 50];

vector <int> p;

void getPrime()

{

    // 华丽的初始化

    memset(noprime, false, sizeof(noprime));

    p.clear();

    int m = (int)sqrt(maxn + 0.5);

    // 优化的埃筛

    for (int i = 2; i <= m; i++)

    {

        if (!noprime[i])

        {

            for (int j = i * i; j <= maxn; j += i)

            {

                noprime[j] = true;

            }

        }

    }

}

std::vector<pii> v;

int main()

{

    //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);

    //freopen("D:\\common_text\code_stream\\out.txt","w",stdout);

    getPrime();

    int n;

    gbtb;

    cin >> n;

    if (!noprime[n])

    {

        cout << n << endl;

        repd(i, 2, n)

        {

            cout << i << " " << i - 1 << endl;

        }

        cout << 1 << " " << n << endl;

    } else

    {

        int ans = n;

        int t = ans;

        while (noprime[t])

        {

            t++;

        }

        cout << t << endl;

        repd(i, 2, n)

        {

            cout << i << " " << i - 1 << endl;

        }

        cout << 1 << " " << n << endl;

        int id = 1;

        while (noprime[ans])

        {

            ans++;

            cout << id << " " << id + n / 2 << endl;

            id++;

        }

    }

    return 0;

}

inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '0');

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 - ch + '0';

        }

    }

    else {

        *p = ch - '0';

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 + ch - '0';

        }

    }

}

巴特西

Codeforces Global Round 4 Prime Graph CodeForces - 1178D （构造，结论）

最新文章

热门文章