#include <iostream>
#include <random>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <cstdlib>
#include <ctime>
#include <time.h>
#include<windows.h>
using namespace std;

const int MAXN = 1<<14;

int i_rand = 0;
int i_sum = 0;
int i_rang = 0;

int parent[MAXN];
int rang[MAXN];
int sum[MAXN];

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

int find_set(int v) {
    i_rand++;
    i_rang++;
    i_sum++;
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets_random(int a, int b) {
    a = find_set(a);
    b = find_set(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(a);
    b = find_set(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_sum(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a == b) {
        return;
    }
    if (sum[a] < sum[b]) {
        swap(a, b);
    }
    parent[b] = a;
    sum[a] += sum[b];
}


void random_inp(int n) {
    srand(1234567);
    i_rand = 0;
    i_rang = 0;
    i_sum = 0;
    for (size_t i = 0; i < MAXN; ++i) {
        make_set(i);
    }
    for (size_t i = 0; i < n; ++i) {
        int x = rand() % MAXN, y = rand() % MAXN;
        x = find_set(x);
        y = find_set(y);
        union_sets_random(x, y);
    }
    cout << "random na randome " << i_rand << "\n";
    i_rand = 0;
    i_rang = 0;
    i_sum = 0;
    srand(134567);
    for (size_t i = 0; i < MAXN; ++i) {
        make_set(i);
    }
    for (size_t i = 0; i < n; ++i) {
        int x = rand() % MAXN, y = rand() % MAXN;
        x = find_set(x);
        y = find_set(y);
        union_sets_sum(x, y);
    }
    cout << "random na summe " << i_sum << "\n";
    i_rand = 0;
    i_rang = 0;
    i_sum = 0;
    srand(123457);
    for (size_t i = 0; i < MAXN; ++i) {
        make_set(i);
    }
    for (size_t i = 0; i < n; ++i) {
        int x = rand() % MAXN, y = rand() % MAXN;
        x = find_set(x);
        y = find_set(y);
        union_sets_rang(x, y);
    }
    cout << "random na visote " << i_rang << "\n";
}

void small_to_big() {
    i_rand = 0;
    i_rang = 0;
    i_sum = 0;
    for (size_t i = 0; i < MAXN; ++i) {
        make_set(i);
    }
    for (size_t i = 1; i < MAXN; ++i) {
        int x = 0, y = i;
        x = find_set(x);
        y = find_set(y);
        union_sets_random(x, y);
    }
    cout << "small_to_big na randome " << i_rand << "\n";
    i_rand = 0;
    i_rang = 0;
    i_sum = 0;
    for (size_t i = 0; i < MAXN; ++i) {
        make_set(i);
    }
    for (size_t i = 1; i < MAXN; ++i) {
        int x = 0, y = i;
        x = find_set(x);
        y = find_set(y);
        union_sets_sum(x, y);
    }
    cout << "small_to_big na summe " << i_sum << "\n";
    i_rand = 0;
    i_rang = 0;
    i_sum = 0;
    for (size_t i = 0; i < MAXN; ++i) {
        make_set(i);
    }
    for (size_t i = 1; i < MAXN; ++i) {
        int x = 0, y = i;
        x = find_set(x);
        y = find_set(y);
        union_sets_rang(x, y);
    }
    cout << "small_to_big na visote " << i_rang << "\n";
}

vector<pair<int, int> > q;

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

void equal_to_equal() {
    i_rand = 0;
    i_rang = 0;
    i_sum = 0;
    for (size_t i = 0; i < MAXN; ++i) {
        make_set(i);
    }
    for (size_t i = 1; i < q.size(); ++i) {
        int x = q[i].first, y = q[i].second;
        x = find_set(x);
        y = find_set(y);
        union_sets_random(x, y);
    }
    cout << "equal in random " << i_rand << "\n";
    i_rand = 0;
    i_rang = 0;
    i_sum = 0;
    for (size_t i = 0; i < MAXN; ++i) {
        make_set(i);
    }
    for (size_t i = 1; i < q.size(); ++i) {
        int x = q[i].first, y = q[i].second;
        x = find_set(x);
        y = find_set(y);
        union_sets_rang(x, y);
    }
    cout << "equal in rang " << i_rang << "\n";
    i_rand = 0;
    i_rang = 0;
    i_sum = 0;
    for (size_t i = 0; i < MAXN; ++i) {
        make_set(i);
    }
    for (size_t i = 1; i < q.size(); ++i) {
        int x = q[i].first, y = q[i].second;
        x = find_set(x);
        y = find_set(y);
        union_sets_sum(x, y);
    }
    cout << "equal in sum " << i_sum << "\n";
}


int main() {
    int n;
    cin >> n;
    cout << "Randomniy dannie\n";
    random_inp(n);
    cout << "\n\n\n";
    cout << "One to big\n";
    small_to_big();
    cout << "\n\n\n";
    merge(2);
    cout << "Equal to equal\n";
    equal_to_equal();
    return 0;
}