Test for the Clique Problem#1879

Test for the Clique Problem

1 second

64 megabytes

Medium

In this task, you are given a solution for the problem Cliques.

This solution does not achieve an Accepted status, but it operates with a time complexity of $O (2^{N})$ O(2^N).

// i - current vertex, p - current set of vertices
long long go(int i, long long p) {
    if (p == 0) // if the set p is empty
        return 1;
    counter++; // program execution time
    while (((p >> i) & 1) == 0) // whether vertex i is in set p
        i++;
    p ^= 1LL << i; // exclude vertex i from set p
    if ((p & c[i]) == p) // c[i] - set of vertices connected with vertex i by an edge
        return 2 * go(i, p); // p & c[i] - intersection of sets p and c[i]
    return go(i, p) + go(i, p & c[i]);
}
counter = 0; // reset program execution time
result = go(0, (1LL << n) - 1); // start from the set of all vertices

Your task is to create a test where this solution will not complete within the Time Limit. The runtime of the program is determined by the value of the variable counter.

Input

The number $N$ — the number of vertices in the graph you need to construct.

There are a total of $2$ tests in this task.

The first test has $N = 20$ N = 20. In this test, the variable counter at the end of the program should be at least $5000$ .

The second test has $N = 40$ N = 40. In this test, the variable counter at the end of the program should be at least $50000000$ .

Output

Output the test. The test should conform to the input data format of the problem Cliques.

Examples

Example 1