#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctime>
#include "rts.h"
using namespace std;
typedef long long ll;
#define N 300002
int id[N], fa[N], son[N][2], mn[N], mx[N], ansfa[N];
bool vis[N];
inline bool isroot(int x) {
    return x != son[fa[x]][0] && x != son[fa[x]][1];
}
inline bool getlr(int x) {
    return son[fa[x]][1] == x;
}
inline void pushup(int x) {
    mn[x] = son[x][0] ? mn[son[x][0]] : x;
    mx[x] = son[x][1] ? mx[son[x][1]] : x;
}
inline void rota(int x) {
    int f = fa[x], ff = fa[f], w = getlr(x);

    if (!isroot(f))
        son[ff][getlr(f)] = x;

    son[f][w] = son[x][w ^ 1];
    fa[son[x][w ^ 1]] = f;
    son[x][w ^ 1] = f;
    fa[x] = ff, fa[f] = x;
    pushup(f), pushup(x);
}
inline void splay(int x) {
    for (register int f = fa[x]; !isroot(x); f = fa[x]) {
        if (!isroot(f))
            rota(getlr(f) == getlr(x) ? f : x);

        rota(x);
    }
}
inline int fdrt(int x) {
    while (!isroot(x))
        x = fa[x];

    return x;
}
inline void access(int x) {
    int t = 0;

    while (x) {
        splay(x);
        son[x][1] = t;
        pushup(x);
        t = x, x = fa[x];
    }
}
void play(int n, int T, int dataType) {
    srand(time(NULL));
    int cnt = 0;

    for (int i = 2; i <= n; i++)
        id[i] = i;

    random_shuffle(id + 2, id + 1 + n);
    vis[1] = 1;

    if (dataType == 3) {
        int le = 1, ri = 1;

        for (int i = 2; i <= n; i++)
            if (!vis[id[i]]) {
                int x = id[i];
                int te = explore(le, x);

                if (vis[te]) {
                    te = explore(ri, x);
                    vis[te] = 1;

                    while (te != x)
                        te = explore(te, x), vis[te] = 1;

                    ri = x;
                } else {
                    vis[te] = 1;

                    while (te != x)
                        te = explore(te, x), vis[te] = 1;

                    le = x;
                }
            }

        return;
    }

    for (int i = 1; i <= n; i++)
        mn[i] = mx[i] = i;

    for (int i = 2; i <= n; i++)
        if (!vis[id[i]]) {
            int x = fdrt(1), tt = 1, ii = id[i];

            while (x ^ ii) {
                int te = explore(x, ii);
                cnt++;

                if (!vis[te]) {
                    fa[te] = x;
                    vis[te] = 1;
                    tt = te;
                }

                if (son[x][1] && te == mn[son[x][1]])
                    x = son[x][1];
                else if (son[x][0] && te == mx[son[x][0]])
                    x = son[x][0];
                else
                    x = fdrt(te);
            }

            access(ii);
        }
}