#include <iostream>
#include <random>
#include <vector>
#include <algorithm>
using namespace std;

const int length = 1<<16;

int i_rand = 0;
int i_rang = 0;
int i_cnt = 0;

vector<int> parent(length);
vector<int> rang(length);
vector<int> cnt(length);

vector<pair<int, int>> q, w, e;

void make_set(int v) {
    parent[v] = v;
    rang[v] = 1;
    cnt[v] = 1;
}

void make_elem() {
    for (size_t i = 0; i < length; ++i) {
        make_set(i);
    }
}

int find_set_rand(int v) {
    i_rand++;
    if (v == parent[v])
        return v;
    return parent[v] = find_set_rand(parent[v]);
}

int find_set_rang(int v) {
    i_rang++;
    if (v == parent[v])
        return v;
    return parent[v] = find_set_rang(parent[v]);
}

int find_set_cnt(int v) {
    i_cnt++;
    if (v == parent[v])
        return v;
    return parent[v] = find_set_cnt(parent[v]);
}

void union_sets_rand(int a, int b) {
    a = find_set_rand(a);
    b = find_set_rand(b);
    if (a == b) {
        return;
    }
    srand(b);
    int random = rand() % 2;
    if (random == 0) {
        parent[a] = b;
    }
    else {
        parent[b] = a;
    }
}

void union_sets_rang(int a, int b) {
    a = find_set_rang(a);
    b = find_set_rang(b);
    if (a == b) {
        return;
    }
    if (rang[a] < rang[b]) {
        swap(a, b);
    }
    parent[b] = a;
    if (rang[a] == rang[b]) {
        rang[a]++;
    }
}

void union_sets_cnt(int a, int b) {
    a = find_set_cnt(a);
    b = find_set_cnt(b);
    if (a == b) {
        return;
    }
    if (cnt[a] < cnt[b]) {
        swap(a, b);
    }
    parent[b] = a;
    cnt[a] += cnt[b];
}

void merge (int l) {
    if (l > length) {
        return;
    }
    for (size_t i = 0; i < length - l + 1; i += l) {
        q.push_back(make_pair(i, i + l - 1));
    }
    merge(l * 2);
}

void rand(int n) {
    for (size_t i = 0; i < n; ++i) {
        int x = rand() % length;
        int y = rand() % length;
        w.push_back(make_pair(x, y));
    }
}

void step() {
    for (size_t i = 1; i < length; ++i) {
        int x = i - 1;
        int y = i;
        e.push_back(make_pair(x, y));
    }
}

void test_function(vector<pair<int,int>>& a) {
    i_rand = 0;
    i_rang = 0;
    i_cnt = 0;
    make_elem();
    for (size_t i = 0; i < a.size(); ++i) {
        int x = a[i].first;
        int y = a[i].second;
        x = find_set_rand(x);
        y = find_set_rand(y);
        union_sets_rand(x, y);
    }
    cout << "Random union: " << i_rand << "\n";
    make_elem();
    for (size_t i = 0; i < a.size(); ++i) {
        int x = a[i].first;
        int y = a[i].second;
        x = find_set_rang(x);
        y = find_set_rang(y);
        union_sets_rang(x, y);
    }
    cout << "Rang union: " << i_rang << "\n";
    make_elem();
    for (size_t i = 0; i < a.size(); ++i) {
        int x = a[i].first;
        int y = a[i].second;
        x = find_set_cnt(x);
        y = find_set_cnt(y);
        union_sets_cnt(x, y);
    }
    cout << "Count union: " << i_cnt << "\n";
}


int main() {
    int n;
    cin >> n;
    cout << "Random test\n";
    rand(n);
    test_function(w);
    cout << "\n";
    cout << "Different size test\n";
    step();
    test_function(e);
    cout << "\n";
    cout << "Equal size test\n";
    merge(2);
    test_function(q);
    return 0;
}