#include <bits/stdc++.h>
#include "rts.h"
#define N 341468
using namespace std;

int n;
int ord[N];
char known[N];

namespace LCT{
	#define pa p[nd]
	#define C(x) c[x][nd]
	struct node {int Min, Max, c[2], p;} nd[N];

	inline int dir(int x) {return nd[x].p ? (x == nd[x].pa.c[0] ? 0 : x == nd[x].pa.c[1] ? 1 : -1) : -1;}

	void update(int x){
		nd[x].Min = (nd[x].c[0] ? nd[x].C(0).Min : x);
		nd[x].Max = (nd[x].c[1] ? nd[x].C(1).Max : x);
	}

	void rotate(int x){
		int y = nd[x].p, d = !dir(x);
		nd[nd[y].c[!d] = nd[x].c[d]].p = y;
		nd[x].p = nd[y].p;
		if(~dir(y)) nd[y].pa.c[dir(y)] = x;
		nd[nd[x].c[d] = y].p = x;
		update(y);
	}

	void splay(int x){
		for(; ~dir(x); rotate(x))
			if(~dir(nd[x].p)) rotate(dir(x) ^ dir(nd[x].p) ? x : nd[x].p);
		update(x);
	}

	void access(int x){
		for(int y = 0; x; y = x, x = nd[x].p){
			splay(x); nd[x].c[1] = y; update(x);
		}
	}
}

void tree(){
	using namespace LCT;
	int i, j, x, y;
	for(j = 2; j <= n; ++j)
		if(!known[i = ord[j]]){
			splay(1);
			for(x = 1; x != i; ){
				y = explore(x, i);
				if(y == nd[x].C(0).Max) x = nd[x].c[0]; // left tree
				else if(y == nd[x].C(1).Min) x = nd[x].c[1];
				else{
					if(!known[y]) nd[y].p = x;
					known[y] = 1;
					splay(x = y);
				}
			}
			access(x);
		}
}

void chain(){
	int l = 1, r = 1, i, j, x;
	for(j = 2; j <= n; ++j)
		if(!known[i = ord[j]]){
			known[x = explore(l, i)] ? (x = r, r = i) : (l = i);
			for(; x != i; x = explore(x, i)) known[x] = 1;
			known[x] = 1;
		}
}

void play(int n, int T, int dataType){
	// random
	char *_ptr = new char; srand(time(NULL) + (long long)_ptr); delete _ptr;
	// shuffle
	for(int i = 2; i <= n; ++i) ord[i] = i; random_shuffle(ord + 2, ord + (n + 1));
	// init
	::n = n; known[1] = 1;
	// play
	dataType == 3 ? chain() : tree();
}