1
#include<bits/stdc++.h>
2
#define int long long
3
using i64 = long long;
4

5
std::mt19937 rnd(std::chrono::steady_clock().now().time_since_epoch().count());
6

7
int rng(int l, int r) { // [l, r]
8
    return rnd() % (r - l + 1) + l;
9
}
10

11
void array(int n) { // Generates an array with n elements
12
    int m = 1E9;
13
    std::vector<int> a(n);
14
    for (int i = 0; i < n; i++) {
15
        a[i] = rng(0, m);
16
        std::cout << a[i] << " \n"[i == n - 1];
17
    }
18
}
19

20
void cand(int m, int n) { // Generate m cands from 1 to n
21
    for (int i = 0; i < m; i++) {
22
        int l = rng(1, n);
23
        int r = rng(1, n);
24

25
        if (l > r) {
26
            std::swap(l, r);
27
        }
28

29
        std::cout << l << " " << r << "\n";
30
    }
31
}
32

33
void tree(int n) { // Generate a tree with n vertices
34
    int m = 1E9;
35
    for (int i = 1; i < n; i++) {
36
        int p = rng(0, i - 1);
37
        int v = rng(1, m);
38
        std::cout << p + 1 << " " << i + 1 << " " << v << "\n";
39
    }
40
}
41

42
void graph(int n, int m) {
43
// Generate an undirected graph with n vertices and m edges. There are no double edges or self-rings in the graph, and must be connected.
44
    std::vector<std::pair<int, int>> e;
45
    std::map<std::pair<int, int>, bool> f;
46

47
    std::cout << n << " " << m << "\n";
48

49
    for (int i = 1; i < n; i++) {
50
        int p = rng(0, i - 1);
51
        e.push_back(std::make_pair(p, i));
52
        f[std::make_pair(p, i)] = f[std::make_pair(i, p)] = true;
53
    }
54

55
    // debug(f);
56
    for (int i = n; i <= m; i++) {
57
        int x, y;
58
        do {
59
            x = rng(0, n - 1);
60
            y = rng(0, n - 1);
61
        } while (x == y || f.count(std::make_pair(x, y)));
62

63
        e.push_back(std::make_pair(x, y));
64
        f[std::make_pair(x, y)] = f[std::make_pair(y, x)] = true;
65
    }
66

67
    std::shuffle(e.begin(), e.end(), rnd);
68

69
    for (auto [x, y] : e) {
70
        std::cout << x + 1 << " " << y + 1 << "\n";
71
    }
72
}
73

74
signed main() {
75
    int t = 5;
76
    std::cout << t << "\n";
77

78
    while (t--) {
79
        graph(3, 3);
80
    }
81

82
    return 0;
83
}