#include "sonlib.h"


////////////////////////////////////////////////////////////////////////////////
// AMALGAMATE: "include/template.hpp" BEGINS HERE
//
	
	
	#include <bits/stdc++.h>
	using namespace std;
	
	
	////////////////////////////////////////////////////////////////////////////////
	// AMALGAMATE: "include/abbrevs.hpp" BEGINS HERE
	//
		
		#define UI unsigned int
		
		#define LL long long
		#define ULL unsigned long long
		
		#define PII pair<int,int>
		
		
		#define RI ri()
		#define RUI rui()
		
		#define RLL rll()
		#define RULL rull()
		
		#define RSTR rstr()
		
		
		
		#define FO(i,a,b) for(int i=(a); i<int(b); ++i)
		#define OF(i,a,b) for(int i=(b)-1; i>=int(a); --i)
		
		#define FOR(i,n) FO(i,0,n)
		#define ROF(i,n) OF(i,0,n)
		
		
		#define MIN(a,b) ((a)<(b) ? (a) : (b))
		#define MAX(a,b) ((b)<(a) ? (a) : (b))
		
		#define REMIN(a,b) ((a) = min(a,b))
		#define REMAX(a,b) ((a) = max(a,b))
		
		#define ALL(c) (c).begin(),(c).end()
		
		#define SQR(x) ((x)*(x))
		
		
		
		bool is_pow(int x) {
			return (x&(x-1)) == 0;
		}

		template<class T>
		int sgn(const T& x) {
			if(x > 0) return 1;
			if(x < 0) return -1;
			return 0;
		}
		
	
	//
	// AMALGAMATE: "include/abbrevs.hpp" ENDS HERE
	////////////////////////////////////////////////////////////////////////////////
	
	
	
	

//
// AMALGAMATE: "include/template.hpp" ENDS HERE
////////////////////////////////////////////////////////////////////////////////





class UF {
	struct Node {
		int parent;

		//
		// per-set data - EDIT HERE
		int size = 1;
		void on_merge_from(const Node& o) { // called by UF implementation
			size += o.size;
		}
		//


		//
		// path aggreg - EDIT HERE
		//
		// If at any point you're calling merge(some_non_root, b),
		// path aggregation isn't real path aggregation,
		// but instead can aggregate paths that go back and forth,
		// visiting some vertices several times.
		// This works for e.g. XOR-ing edge weights,
		// or any other involution (OP == OP^-1)
		//
		// It's meant for edge aggregation. For vertices,
		// the code would require some changes.
		//
		// When calling merge(a,b), that is creating a new edge,
		// be sure to aggregate this edge *after* merging, like this:
		//   uf.merge(a,b);
		//   uf[a].path_edges_parity = 1;
		//
		//bool path_edges_parity = 0;
		void on_path_aggreg(const Node& /* o */) { // called by UF implementation
			//path_edges_parity ^= o.path_edges_parity;
		}
		//

	};
	vector<Node> v;

public:
	UF(int sz) : v(sz) {
		FOR(i,sz) v[i].parent = i;
	}

	int find(int x) {
		if(v[x].parent == x) return x;

		int parent = v[x].parent;
		int root = find( parent );
		v[x].on_path_aggreg( v[parent] );
		v[x].parent = root;

		return root;
	}


	void merge(int a, int b) {
		int fa = find(a);
		int fb = find(b);
		if(fa == fb) return;

		v[fa].parent = a;
		v[fa].on_path_aggreg( v[a] );

		v[a].parent = b;

		v[fb].on_merge_from( v[fa] );
	}

	// helpers
	bool same(int a, int b) { return find(a) == find(b); }
	Node& find_node(int x) { return v[ find(x) ]; }
	auto& operator[](int a) { return v[ find(a) ]; }
};

UF uf(404);






#define cerr if(0)cerr


int N;
char _g[404][404];
int num_edges = 0;
int curr = 0;
int parity = 0;

bool examined[404];
int num_examined = 0;

int num_moves = 0;

bool has_edge(int a, int b) { return _g[a][b] == 1; }
bool no_edge(int a, int b) { return _g[a][b] == -1; }

void add_edge(int a, int b) {
	assert(a != b);
	assert(!no_edge(a,b));
	if(has_edge(a,b)) return;

	_g[a][b] = 1;
	_g[b][a] = 1;
	++num_edges;

	cerr << "discovered edge " << a << " -- " << b << endl;

	uf.merge(a,b);
}

bool has_spantree() {
	return uf[0].size == N;
}

void remove_edge(int a, int b) {
	assert(!has_edge(a,b));
	if(no_edge(a,b)) return;

	_g[a][b] = -1;
	_g[b][a] = -1;
}



int _remap(int x) {

	// return x;

	static vector<int> v;
	if(v.empty()) {
		v.resize(N);
		FOR(i,N) v[i] = i;
		random_shuffle(v.begin()+1, v.end());
	}
	return v[x];
}



bool move_probe(int v) {
	cerr << "move probe to " << v << endl;

	bool known_edge = false;
	if(curr != -1 && has_edge(curr,v)) known_edge = true;

	bool known_no_edge = false;
	if(curr != -1 && no_edge(curr,v)) known_no_edge = true;

	auto r = MoveProbe(_remap(v)+1);
	++num_moves;

	if(parity == 1 && !r) {
		if(curr != -1) remove_edge(curr, v);
	}
	else if(r || known_edge) {
		if(curr != -1) add_edge(curr, v);
		curr = v;
		if(curr != -1 && !examined[curr]) {
			examined[curr] = true;
			++num_examined;
			Examine();
		}
	}
	else {
		curr = -1;
	}

	if(r) {
		parity = 0;
	}
	else if(known_edge) {
		parity = 1;
	}
	else if(known_no_edge) {
	}
	else if(!r && parity == 1) {
	}
	else {
		parity = -1;
	}

	return r;
}
#define MoveProbe move_probe // just in case







void solve_diamond(int fr, deque<int> mids, int to) {
	cerr << "detected diamond " << fr << " <-(" << mids.size() << " cands)-> " << to << endl;
	// probe at `to`

	random_shuffle(ALL(mids)); // just to be safe

	FOR(i_first, mids.size()) {
		auto r = move_probe(mids[i_first]);
		assert(!r);

		FOR(i_next, mids.size()) {
			if(i_next == i_first) continue;

			r = move_probe(mids[i_next]);
			if(r) {
				if(i_next < i_first) {
					add_edge(to, mids[i_first]);
					add_edge(mids[i_first], mids[i_next]);
					return;
				}
				int new_fr = to;
				int new_to = mids[i_next];
				mids.resize(i_next);
				FOR(jj, i_first) mids.pop_front();
				solve_diamond(new_fr, std::move(mids), new_to);
				return;
			}
		}

		r = move_probe(to);
		assert(r);
	}

	cerr << "solve_diamond detected no edges between mids" << endl;

	while((int)mids.size() > 1) {

		cerr << "check mid " << mids[0] << endl;
		auto r = move_probe(mids[0]);
		assert(!r);

		r = move_probe(fr);

		if(r) {
			add_edge(fr, mids[0]);
			add_edge(mids[0], to);
			return;
		}

		FO(i, 1, mids.size()) {
			r = move_probe(mids[i]);
			if(r) {
				cerr << "solve_diamond detected edge between fr and to" << endl;
				add_edge(to, fr);
				add_edge(fr, mids[i]);
				return;
			}
		}

		mids.pop_front();
		r = move_probe(to);
		assert(r);
	}

	cerr << "solve diamond deduced last option " << mids[0] << endl;
	add_edge(fr, mids[0]);
	add_edge(mids[0], to);
}

void solve_star() {
	cerr << "detected star" << endl;
	FO(i, 1, N) {
		add_edge(0,i);
	}
}

void solve_0() {
	FO(first, 1, N) {
		move_probe(first);

		FO(i, 1, N) {
			if(i == first) continue;

			auto r = move_probe(i);
			if(r) {
				if(i < first) {
					add_edge(0, first);
					add_edge(first, i);
					return;
				}
				deque<int> mids;
				FO(jj, first, i) {
					mids.push_back(jj);
				}
				solve_diamond(0, move(mids), i);
				return;
			}
		}

		auto r = move_probe(0);
		assert(r);
	}

	solve_star();
}

bool has_unknown_outs(int v) {
	FOR(dest, N) {
		if(dest == v) continue;
		if(_g[v][dest] == 0) return true;
	}
	return false;
}

bool goto_parity(int want_parity) {
	assert(curr != -1);
	assert(parity != -1);

	struct Node {
		int vert;
		int parity;
	};
	deque<Node> q;

	int came_from[404][2];
	FOR(i,404) FOR(j,2) came_from[i][j] = -1;

	bool visited[404][2];
	FOR(i,404) FOR(j,2) visited[i][j] = false;

	auto push = [&](int from, Node node) {
		// cerr << "push " << node.vert << " " << node.parity << endl;
		auto& vis = visited[node.vert][node.parity];
		if(vis) return;

		came_from[node.vert][node.parity] = from;

		q.push_back(node);
		vis = true;
	};

	push(-1, {curr, parity});

	while(!q.empty()) {
		auto [c_vert, c_parity] = q.front();
		q.pop_front();

		if(c_parity == want_parity && has_unknown_outs(c_vert)) {
			deque<int> path;
			while(c_vert != curr || c_parity != parity) {
				path.push_front(c_vert);
				c_vert = came_from[c_vert][c_parity];
				c_parity = !c_parity;
			}

			cerr << "found path to parity " << want_parity << ":" << endl;
			cerr << curr << " -> ";
			for(auto& v : path) cerr << v << " ";
			cerr << endl;

			assert(path.size() % 2 == parity ^ want_parity);

			for(auto& v : path) move_probe(v);
			return true;
		}

		FOR(dest, N) {
			if(!has_edge(c_vert, dest)) continue;

			push(c_vert, {dest, !c_parity});
		}
	}

	return false;
}

bool goto_nonexamined() {
	assert(curr != -1);
	assert(parity != -1);

	bool visited[404];
	FOR(i, 404) visited[i] = false;

	deque<int> q;

	vector<int> came_from(404);
	for(auto& e : came_from) e = -1;

	auto push = [&](int from, int dest) {
		if(visited[dest]) return;

		came_from[dest] = from;
		visited[dest] = true;
		q.push_back(dest);
	};

	push(-1, curr);

	while(!q.empty()) {
		auto c_vert = q.front();
		q.pop_front();

		if(!examined[c_vert]) {
			deque<int> path;
			while(c_vert != curr) {
				path.push_front(c_vert);
				c_vert = came_from[c_vert];
			}
			for(auto& v : path) move_probe(v);
			return true;
		}

		FOR(dest, N) {
			if(!has_edge(c_vert, dest)) continue;
			push(c_vert, dest);
		}
	}

	return false;
}


void odd_discover() {
	cerr << "odd_discover at " << curr << " (parity " << parity << ")" << endl;

	assert(parity == 1);
	assert(curr != -1);

	auto v0 = curr;

	FOR(dest, N) {
		assert(parity == 1);
		assert(curr == v0);

		if(dest == curr) continue;
		if(_g[curr][dest] != 0) continue;

		cerr << "odd discover " << curr << " -> " << dest << endl;
		auto r = move_probe(dest);
		if(!r) {
			remove_edge(curr,dest);
			continue;
		}

		add_edge(v0, dest);
		move_probe(v0);
	}

	assert(curr == v0);
	assert(!has_unknown_outs(curr));
}

auto find_any_2(int v0) {
	deque<int> q;

	bool vis[404];
	FOR(i,404) vis[i] = false;

	vector<int> came_from(404);
	for(auto& e : came_from) e = -1;

	auto push = [&](int from, int next) {
		if(vis[next]) return;
		vis[next] = true;
		came_from[next] = from;
		q.push_back(next);
	};

	push(-1, v0);

	while(!q.empty()) {
		auto c_vert = q.front();
		q.pop_front();

		if(c_vert != v0 && came_from[c_vert] != v0) {
			deque<int> path;
			while(c_vert != curr) {
				path.push_front(c_vert);
				c_vert = came_from[c_vert];
			}
			assert(path.size() == 2);
			return pair{path[0], path[1]};
		}

		FOR(dest, N) {
			if(!has_edge(c_vert, dest)) continue;
			push(c_vert, dest);
		}
	}

	cerr << "unable to find path with length 2" << endl;
	abort();
}

void even_discover() {
	cerr << "even_discover (A) at " << curr << endl;

	assert(parity == 0);
	assert(curr != -1);

	auto v0 = curr;

	FOR(dest, N) {
		if(dest == v0) continue;
		if(_g[v0][dest] != 0) continue;

		assert(curr == v0);
		assert(parity == 0);

		int dest2 = -1;

		FOR(i, N) {
			if(i == dest) continue;
			if(!has_edge(dest, i)) continue;

			dest2 = i;
		}

		if(dest2 == -1) continue;

		move_probe(dest);
		auto r = move_probe(dest2);
		if(r) {
			add_edge(v0, dest);
			move_probe(dest);
			r = move_probe(v0);
			assert(r);
			return; // try odd_discover again - more efficient
		}
		else {
			remove_edge(v0, dest);
			r = move_probe(dest);
			if(r) {
				add_edge(v0, dest2);
				move_probe(dest2);
				r = move_probe(v0);
				assert(r);
				return; // try odd_discover again - more efficient
			}
			else {
				curr = v0;
				parity = 0;
			}
		}
	}

	cerr << "even_discover (B) at " << curr << endl;

	auto [v1, v2] = find_any_2(v0);

	FOR(dest, N) {
		if(dest == v0) continue;
		if(_g[v0][dest] != 0) continue;

		assert(curr == v0);
		assert(parity == 0);

		move_probe(dest);
		auto r = move_probe(v2);
		if(r) {
			add_edge(v0, dest);
			add_edge(dest, v2);
			return; // try odd_discover again - more efficient
		}

		move_probe(v1);
		r = move_probe(v2);
		if(r) {
			remove_edge(v0, dest);
			move_probe(v1);
			r = move_probe(v0);
			assert(r);
		}
		else {
			add_edge(v0, dest);
			r = move_probe(v0);
			assert(r);
		}
	}

	assert(!has_unknown_outs(curr));
}


int main() {
	N = GetN();

	// GetSubtask(); // for losers

	solve_0();

	cerr << "have " << num_edges << " edges after solve_0()" << endl;

	assert(num_edges >= 2);

	while(!has_spantree()) {
		auto r = goto_parity(1);
		if(r) {
			odd_discover();
			continue;
		}

		r = goto_parity(0);
		assert(r);
		even_discover();
		continue;

		// cerr << "error: nothing worked!" << endl;
		// exit(1);
	}

	while(num_examined < N) {
		auto r = goto_nonexamined();
		assert(r);
	}

	cerr << "num examined: " << num_examined << " / " << N << endl;

	cerr << "num moves: " << num_moves << endl;

	return 0;
}