#include <cstdio>
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;
const int n = 1000000, m = 2000000;
int a[m],b[m],i,p1[n],p2[n],size[n];
double start, finish;
int Find2(int v){
    if(v == p2[v])
        return v;
    return p2[v] = Find2(p2[v]);
}
void Union2(int a, int b){
    a = Find2(a);
    b = Find2(b);
    if(a == b)
        return;
    if(size[a] < size[b])
        swap(a, b);
    size[a] += size[b];
    p2[b] = a;
}
int Find1(int v){
    if(v == p1[v])
        return v;
    return p1[v] = Find1(p1[v]);
}
void Union1(int a, int b){
    a = Find1(a);
    b = Find1(b);
    if(a == b)
        return;
    if(rand() % 2)
        swap(a, b);
    p1[b] = a;
}
int main(){
    freopen("input.txt","r",stdin);
    ios_base :: sync_with_stdio(0);
    cin.tie();
    srand(time(0));
    for(i = 0; i < m; i++){
        a[i] = (rand() + (rand() << 15)) % n;
        b[i] = (rand() + (rand() << 15)) % n;
        //cout << a[i] << " " << b[i] << endl;
    }
    for(i = 0; i < n; i++){
        p1[i] = p2[i] = i;
        size[i] = 1;
    }
    start = clock();
    for(i = 0; i < m; i++){
        Union1(a[i], b[i]);
    }
    finish = clock();
    cout << finish - start << endl;

    start = clock();
    for(i = 0; i < m; i++){
        Union2(a[i], b[i]);
    }
    finish = clock();
    cout << finish - start << endl;

    return 0;
}