#include <bits/stdc++.h>

using namespace std;
mt19937 rnd(random_device{}());

// Function to generate a tree structure with `n` nodes
vector<pair<int, int>> generate_tree(unsigned int n) {
    vector<pair<int, int>> edges;
    vector<int> available_nodes, connected_nodes;

    // Initialize available_nodes with 1 to n
    for (int i = 2; i <= n; ++i) {
        available_nodes.push_back(i);
    }
    connected_nodes.push_back(1);  // Start with the root node (1)

    // Connect available nodes to the connected nodes to form a tree
    while (!available_nodes.empty()) {
        int u = connected_nodes[rnd() % connected_nodes.size()];
        int v = available_nodes.back();
        available_nodes.pop_back();
        edges.emplace_back(u, v);
        connected_nodes.push_back(v);
    }

    return edges;
}

// Function to generate `f` paths in the tree with `n` nodes
vector<pair<int, int>> generate_paths(unsigned int f,unsigned int n) {
    vector<pair<int, int>> paths;

    for (int i = 0; i < f; ++i) {
        unsigned int a = rnd() % n + 1;
        unsigned int b = rnd() % n + 1;

        // Ensure that a and b are different
        while (a == b) {
            b = rnd() % n + 1;
        }

        paths.emplace_back(a, b);
    }

    return paths;
}

// Function to write the generated data to a file
void write_to_file(unsigned int n,unsigned int f, const vector<pair<int, int>> &edges, const vector<pair<int, int>> &paths,
                   const string &filename) {
    ofstream outfile(filename);

    // Write the number of nodes and paths
    outfile << n << " " << f << endl;

    // Write the edges of the tree
    for (const auto &edge: edges) {
        outfile << edge.first << " " << edge.second << endl;
    }

    // Write the paths
    for (const auto &path: paths) {
        outfile << path.first << " " << path.second << endl;
    }

    outfile.close();
}

int main() {
    // Example sizes for n and f (these can be adjusted as needed)
    unsigned int n = 10;  // Number of nodes (from 2 to 100000)
    unsigned int f = rnd() % 10 + 1;  // Number of paths (from 1 to 100000)

    // Generate the tree and paths
    vector<pair<int, int>> edges = generate_tree(n);
    vector<pair<int, int>> paths = generate_paths(f, n);

    // Write the generated data to a file
    write_to_file(n, f, edges, paths, "input.txt");

    cout << "Input data generated and written to input.txt" << endl;

    return 0;
}