#include <bits/stdc++.h> // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates
#include "sonlib.h"

struct Subtask1 {
	int n;

	Subtask1()
		: n(GetN())
	{
		debug(n);
		Examine();

		vector<bool> left_side(n);
		left_side[0] = true;
		int reverse_order = false;
		while(true) {
			debug() << "trying to find left v";
			debug(left_side);
			vector<int> to_iterate;
			REP(i, n)
				if(not left_side[i])
					to_iterate.emplace_back(i);
			if(reverse_order)
				reverse(to_iterate.begin(), to_iterate.end());
			debug(to_iterate);
			bool found = false;
			REP(i, size(to_iterate))
				if(MoveProbe(to_iterate[i] + 1)) {
					debug() << "stopped at " << to_iterate[i];
					found = true;
					Examine();
					left_side[to_iterate[i]] = true;
					break;
				}
			if(not found) {
				debug() << "breaking";
				assert(MoveProbe(1) == true);
				if(reverse_order == 0)
					reverse_order = 1;
				else {
					break;
					reverse_order = 0;
				}
			}
		}
		REP(i, n)
			if(not left_side[i]) {
				assert(MoveProbe(i + 1) == false);
				Examine();
				assert(MoveProbe(1) == true);
			}
		debug(left_side);
	}
};

struct Subtask2 {
	int n;
	vector<int> parent, depth;
	int good_move = false;
	int curr_vertex = 0;

	void fix_parity_dfs() {
		if(curr_vertex == 0) {
			MoveProbe(2);
			MoveProbe(3);
			MoveProbe(1);
			return;
		}

		int v = curr_vertex;
		MoveProbe(parent[v] + 1);
		curr_vertex = parent[v];
		fix_parity_dfs();
		curr_vertex = v;
		MoveProbe(v + 1);
	}

	void fix_parity() {
		if(good_move == false) {
			fix_parity_dfs();
			good_move = true;
		}
	}

	bool make_move(int v) {
		fix_parity();
		if(MoveProbe(v + 1)) {
			curr_vertex = v;
			good_move ^= 1;
			return true;
		}
		return false;
	}

	void dfs(int v) {
		Examine();
		REP(u, n)
			if(depth[u] == -1)
				if(make_move(u)) {
					depth[u] = depth[v] + 1;
					parent[u] = v;
					dfs(u);
					make_move(v);
				}
	}

	Subtask2()
		: n(GetN()),
		parent(n, -1),
		depth(n, -1)
	{
		depth[0] = 0;
		dfs(0);
	}
};

struct Subtask3 {
	int n;

	vector<int> sztos = {0};
	vector<int> right2, left2;
	vector<bool> examined;
	vector<vector<int>> seq;

	void just_visited(int v) {
		debug();
		debug() << "just entered " << v + 1;
		debug() << "state: ";
		debug(sztos, examined);
		debug(right2, left2);
		debug(seq);

		Examine();
		examined[v] = true;
		sztos.emplace_back(v);

		if(n == 4) {
			left2[0] = v;
			right2[v] = 0;
			return;
		}

		vector<int> perm;
		REP(u, n)
			if(u != v and u != left2[v])
				perm.emplace_back(u);

		auto try_perm = [&](int iterations) {
			debug() << "trying permutation " << perm << " (x" << iterations << ')';
			if(iterations == 2) {
				int s = int(perm.size());
				REP(i, s)
					perm.emplace_back(perm[i]);
			}
			for(int i = 0; i < int(perm.size()); ++i) {
				int u = perm[i];
				if(MoveProbe(u + 1)) {
					right2[v] = u;
					left2[u] = v;
					debug() << "found next neighbor of " << v + 1;
					debug() << "going recursively to " << u + 1 << " for now";
					perm.resize(i + 1);
					seq[v] = perm;
					if(u != 0)
						just_visited(u);
					return true;
				}
			}
			return false;
		};

		if(try_perm(1))
			return;
		if(MoveProbe(left2[v] + 1)) {
			debug() << "wrong side, trying to come back with perm " << seq[left2[v]];
			for(int u : seq[left2[v]])
				if(MoveProbe(u + 1))
					break;
			reverse(perm.begin(), perm.end());
			assert(try_perm(2));
		}
		else {
			MoveProbe(v + 1);
			assert(try_perm(2));
		}
	}

	Subtask3()
		: n(GetN()),
		right2(n, -1),
		left2(n, -1),
		examined(n, false),
		seq(n)
	{
		if(n == 3) {
			Examine();
			MoveProbe(2);
			Examine();
			MoveProbe(3);
			Examine();
			return;
		}
		// assert(n % 2 == 0);
		Examine();
		examined[0] = true;
		vector<int> seq0;
		REP(it, 2)
			FOR(v, 1, n - 1)
				seq[0].emplace_back(v);
		for(int v : seq[0])
			if(MoveProbe(v + 1)) {
				right2[0] = v;
				left2[v] = 0;
				just_visited(v);
				break;
			}
		assert(n % 2 == 0);
		debug() << '\n' << "now trying to fill gaps";
		debug(sztos);

		vector<int> left(n, -1), right(n, -1);

		for(int i = 0; i < n / 2; ++i) {
			int v = sztos[i];
			bool found = false;
			REP(u, n)
				if(not examined[u] and u != left[v]) {
					MoveProbe(u + 1);
					if(MoveProbe(right2[v] + 1)) {
						MoveProbe(u + 1);
						Examine();
						MoveProbe(right2[v] + 1);
						found = true;
						right[v] = u;
						left[u] = v;
						left[right2[v]] = u;
						right[u] = right2[v];
						debug() << "next to " << v + 1 << " is " << u + 1;
						break;
					}
					else if(i == 0 and MoveProbe(left2[v] + 1)) {
						reverse(sztos.begin(), sztos.end());
						sztos.pop_back();
						sztos.emplace(sztos.begin(), 0);
						debug() << "reversing sztos to " << sztos;
						debug() << "trying again";
						--i;
						found = true;
						break;
					}
				}
			assert(found);
		}
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int s = GetSubtask();
	if(s == 0)
		s = 2;
	if(s == 1)
		Subtask1();
	else if(s == 2)
		Subtask2();
	else if(s == 3)
		Subtask3();
}