#include <iostream>
#include "sonlib.h"
#include <vector>
#include <list>
#include <set>

using namespace std;

list<int> findPathToClosest(const int& n, const vector<vector<int>>& neighbours, 
							const vector<bool>& mids, 
							const vector<bool>& scouts,
							const int& position, int mid,
							const vector<bool>& ancientScouts)
{
	list<int> path;
	list<int> queue;
	vector<int> ancestors(n);
	vector<bool> visited(n);

	if ((mid == 1 && mids[position] == true) || // LF mid and found mid
		(mid == 0 && scouts[position] == true) ||
		(mid == 2 && ancientScouts[position] == true))
		return path;

	for (int i = 0; i < n; i++)
	{
		visited[i] = false;
		ancestors[i] = -1;
	}

	visited[position] = true;
	queue.push_back(position);



	while (queue.size() > 0)
	{	
		for (int i = 0; i < neighbours[queue.front()].size(); i++) {
			
			if (visited[neighbours[queue.front()][i]] == false)
			{
				visited[neighbours[queue.front()][i]] = true;
				queue.push_back(neighbours[queue.front()][i]);
				ancestors[neighbours[queue.front()][i]] = queue.front();
				
				if ((mid == 1 && mids[neighbours[queue.front()][i]] == true) || // LF mid and found mid
				    (mid == 0 && scouts[neighbours[queue.front()][i]] == true) ||
				    (mid == 2 && ancientScouts[neighbours[queue.front()][i]] == true)) // LF scout and found scout
				{
					path.push_front(neighbours[queue.front()][i]);
					int ancestor = ancestors[neighbours[queue.front()][i]];
					
					while (ancestor != -1)
					{
						path.push_front(ancestor);
						ancestor = ancestors[ancestor];
					}
					path.pop_front();
					return path;
				}
			}
		}

		queue.pop_front();
	}

	return path;
}

vector<int> FindTriad(const int n, 
					  vector<vector<int>>& neighbours, 
					  vector<int>& suspects, 
					  int& position,
					  vector<bool>& scouts,
					  set<int>& scoutsList,
					  vector<bool>& mids,
					  set<int>& midsList,
					  vector<bool>& taken,
					  set<int>& unexploredList,
					  bool& starPossible,
					  vector<bool>& ancientScouts,
					  set<int>& ancientScoutsList)
{
	int feedback;
	int home;

	bool hit = false;

	vector<int> rotatedUnexplored(unexploredList.size());

	for (int shift = 0; shift < unexploredList.size(); shift++)
	{
		suspects.clear();
		int k = 0;
		
		for (auto it = unexploredList.begin(); it != unexploredList.end(); ++it)
		{
			rotatedUnexplored[(shift + k) % unexploredList.size()] = *it; //rotating unexplored list to search
			k++;
		}

		for (int i = 0; i < unexploredList.size(); i++)
		{


			feedback = MoveProbe(rotatedUnexplored[i] + 1);

			if (feedback == 1) // nowe miejsce, trzeba sprobowac wrocic do domu
			{

				if (taken[rotatedUnexplored[i]] != true)
				{
					Examine();
					taken[rotatedUnexplored[i]] = true;
					unexploredList.erase(rotatedUnexplored[i]);
					scouts[rotatedUnexplored[i]] = true; // dodajemy do scoutow
					ancientScouts[rotatedUnexplored[i]] = true; // dodajemy do scoutow
					scoutsList.insert(rotatedUnexplored[i]);
					ancientScoutsList.insert(rotatedUnexplored[i]);
					starPossible = false;
				}
				
				home = position;
				position = rotatedUnexplored[i];
				hit = true;
				break;
			}	
			else
			{
				//cout << "silence" << endl;
				suspects.push_back(rotatedUnexplored[i]);
			}
		}

		if (hit == true)
			break;
		
		// powrot do domu (przez sasiada)
		if (neighbours[position].size() > 0) // mam sasiada
		{
			//cout << "najpierw sasiad: " << neighbours[position][0] + 1 << endl;
			feedback = MoveProbe(neighbours[position][0] + 1);
		}
		//cout << "Ide do domu: " << (position) + 1 << endl; 
		feedback = MoveProbe(position + 1);

	}

	if (hit == false) // gwiazda
	{
		if (starPossible == true)
		{
			//cout << "GWIAZDA!" << endl;
			
			for (int i = 1; i < n; i++)
			{
				//cout << "Ide do: " << i + 1 << endl;
				feedback = MoveProbe(i + 1);
				Examine();
				//cout << "Ide do: " << position + 1 << endl;
				feedback = MoveProbe(position + 1);
			}
		}
		else
		{
			scoutsList.erase(position);
			scouts[position] = false;
			vector<int> triad{ position, position, position };
			return triad;
		}
	}

	// FINDING MIDDLE POINT -> TRYING TO GO BACK HOME
	bool newHome = false;
	
	while (true)
	{
		for (int i = 0; i < suspects.size(); i++) // po suspectach
		{
			vector<int> additionalSuspects; // w razie kolejnego nowego domu
			
			//cout << "Ide do: " << suspects[i] + 1 << endl;
			feedback = MoveProbe(suspects[i] + 1);
			//cout << "silence" << endl;
			additionalSuspects.push_back(suspects[i]);

			//cout << "Ide do: " << home + 1 << endl;
			feedback = MoveProbe(home + 1);

			if (feedback == 1)
			{
				//cout << "HIT! DOM" << endl; // ZNALEZIONO DOM*************
				unexploredList.erase(suspects[i]);
				midsList.insert(suspects[i]);
				mids[suspects[i]] = true; // dodajemy mida 
				MoveProbe(suspects[i] + 1);
				
				if (taken[suspects[i]] != true)
				{
					Examine();
					taken[suspects[i]] = true;
				}

				vector<int> triad{ home, suspects[i], position };
				
				// dodanie sasiadow
				neighbours[triad[1]].push_back(triad[0]);
				neighbours[triad[1]].push_back(triad[2]);
				neighbours[triad[0]].push_back(triad[1]);
				neighbours[triad[2]].push_back(triad[1]);


				return triad;
			}
			else
				//cout << "silence" << endl;

			for (int j = 0; j < suspects.size() - 1; j++) // mielimy suspectow do konca
			{

				//cout << "Ide do: " << suspects[(i + j + 1) % n] + 1 << endl; // moze blad z modulu bedzie
				feedback = MoveProbe(suspects[(i + j + 1) % n] + 1);

				if (feedback == 1)
				{

					home = position;
					position = suspects[(i + j + 1) % n];
					
					//cout << "HIT! Nowe miejsce: " << position << " dom: " << home << endl; // NIESTETY NOWY DOM
					if (taken[position] != true)
					{
						Examine();
						taken[position] = true;

						unexploredList.erase(position);
						scouts[position] = true; // dodajemy do scoutow
						ancientScouts[position] = true;
						scoutsList.insert(position);
						ancientScoutsList.insert(position);
					}
					
					newHome = true;
					break;
				}
				else
				{
					//cout << "silence" << endl;
					additionalSuspects.push_back((i + j + 1) % n);
				}
			}
			if (newHome)
			{
				suspects = additionalSuspects;
				break;
			}

			//cout << "Ide do: " << position + 1 << endl; // wracamy do domu
			feedback = MoveProbe(position + 1);
		}
	}
}

void Exploration(const int n,
	vector<vector<int>>& neighbours,
	int& position,
	vector<bool>& taken,
	vector<bool>& scouts,
	set<int>& scoutsList,
	vector<bool>& mids,
	set<int>& midsList,
	set<int>& unexploredList,
	vector<bool>& ancientScouts,
	set<int>& ancientScoutsList)
{
	int feedback;

	list<int> unexploredToAdd;
		
	for (auto it = unexploredList.begin(); it != unexploredList.end(); ++it) // *---\/**/\*
	{
		feedback = MoveProbe(*it + 1);

		if (feedback == 1) // new place
		{		
			//cout << "HIT! Nowe miejsce" << endl;
			if (taken[*it] != true)
			{
				// sasiedzi	
				neighbours[position].push_back(*it);
				neighbours[*it].push_back(position);
				
				Examine();
				taken[*it] = true;
				
				scoutsList.insert(*it);
				ancientScoutsList.insert(*it);
				scouts[*it] = true; // dodajemy do scoutow
				ancientScouts[*it] = true;
				unexploredToAdd.push_back(*it);
			}

			//powrot do poczatku
			feedback = MoveProbe(position + 1);
		}
	}

	for (auto it = unexploredToAdd.begin(); it != unexploredToAdd.end(); ++it)
	{
		unexploredList.erase(*it);
	}

	//usun z midow
	midsList.erase(position);
	mids[position] = false;

}

void SafeProbe(const int n,
	vector<vector<int>>& neighbours,
	int& position,
	vector<bool>& taken,
	vector<bool>& scouts,
	set<int>& scoutsList,
	vector<bool>& mids,
	set<int>& midsList,
	set<int>& unexploredList,
	vector<bool>& ancientScouts,
	set<int>& ancientScoutsList)
{
	int feedback;
	vector<int> rotatedUnexplored(unexploredList.size());
	list<int> unexploredToAdd;

	int k = 0;
	bool isSomething = false;
	int sasiad_bliski, sasiad_dalszy;

	//szukamy najlepszych sasiadow
	for (int i = 0; i < neighbours[position].size(); i++) // sasiedzi probe'a
	{
		sasiad_bliski = neighbours[position][i];
		if (neighbours[sasiad_bliski].size() > 1)
		{
			int j = 0;
			sasiad_dalszy = neighbours[sasiad_bliski][j];
			while (sasiad_dalszy == position)
			{
				sasiad_dalszy = neighbours[sasiad_bliski][j];
				j++;
			}
		}
	}

	//cout << "sasiad blizszy: " << sasiad_bliski << " sasiad dalszy: " << sasiad_dalszy << endl;
	// probkowanie z uzyciem sasiadow
	for (auto it = unexploredList.begin(); it != unexploredList.end(); ++it)
	{


		feedback = MoveProbe(*it + 1);	// probujemy wejsc
		feedback = MoveProbe(sasiad_bliski + 1); // sasiad

		if (feedback == 1) // wspolny sasiad, wlazl tam od razu, wracamy, examine, break
		{
			feedback = MoveProbe(*it + 1);
			Examine();
			unexploredToAdd.push_back(*it);
			feedback = MoveProbe(position + 1);
			continue;
		}

		feedback = MoveProbe(sasiad_dalszy + 1); // sasiad sasiada
		
		if (feedback == 1) // doszlismy do sasiada, nic nie ma LUB SA POLACZENI
		{
			//najpierw sprawdzamy czy uda sie wrocic przez potencjalnego
			feedback = MoveProbe(*it + 1);	// probujemy wejsc
			feedback = MoveProbe(position + 1);
			
			if (feedback == 1) //polaczone, wracamy, examine i szukamy nowych
			{
				feedback = MoveProbe(*it + 1);
				Examine();
				unexploredToAdd.push_back(*it);
				feedback = MoveProbe(position + 1);
				continue;
			}
			else
			{
				//niepolaczone, nic nie bylo LUB SIE ZAKLINOWAL, safe fixing
				feedback = MoveProbe(sasiad_bliski + 1);
				feedback = MoveProbe(sasiad_dalszy + 1);
			}
			
			
			feedback = MoveProbe(sasiad_bliski + 1); // sasiad
			feedback = MoveProbe(position + 1); // powrot
		}
		else // bylo cos, examine 
		{
			// jestesmy tu ciagle
			Examine();
			unexploredToAdd.push_back(*it);	
			feedback = MoveProbe(position + 1); // powrot
		}
	}

	for (auto it = unexploredToAdd.begin(); it != unexploredToAdd.end(); ++it)
	{
		unexploredList.erase(*it);
	}

	//usun scoutow
	ancientScoutsList.erase(position);
	ancientScouts[position] = false;
}


int main() 
{
	const int n = GetN();
	
	vector<vector<int>> neighbours(n);
	vector<bool> mids(n);
	vector<bool> scouts(n);
	vector<bool> ancientScouts(n);
	set<int> midsList;
	set<int> scoutsList;
	set<int> ancientScoutsList;
	vector<bool> taken(n);
	vector<bool> unexplored(n);
	set<int> unexploredList;
	list<int> path;

	// init

	for (int i = 1; i < n; i++)
	{
		unexplored[i] == true;
		unexploredList.insert(i);
	}

	int currentPosition = 0, home = 0;

	int feedback;
	
	Examine();
	taken[currentPosition] = true;

	// Search for triad

	vector<int> suspects;

	//add 0 to scouts
	scouts[0] = true;
	ancientScouts[0] = true;
	scoutsList.insert(0);
	ancientScoutsList.insert(0);
	bool starPossible = true;

	while (1)
	{
		if (midsList.size() > 0) 
		{
			//go to closest mid
			path = findPathToClosest(n, neighbours, mids, scouts, currentPosition, 1, ancientScouts);

			for (auto it = path.begin(); it != path.end(); ++it)
			{
				feedback = MoveProbe(*it + 1);
				currentPosition = *it;
			}

			//explore from mid
			Exploration(n, neighbours, currentPosition, taken, scouts, scoutsList, mids, midsList, unexploredList, ancientScouts, ancientScoutsList);
		}
		else if (scoutsList.size() > 0) // gwiazda obsluzona
		{
			// go to closest scout
			path = findPathToClosest(n, neighbours, mids, scouts, currentPosition, 0, ancientScouts);

			for (auto it = path.begin(); it != path.end(); ++it)
			{
				feedback = MoveProbe(*it + 1);
				currentPosition = *it;
			}

			// triad search from it
			//triad = { home, suspects[i], position };
			
			// nie spocznie poki nie znajdzie, przy okazji dodajac duzo nowych scoutow i explorujac 
			vector<int> triad = FindTriad(n, neighbours, suspects, currentPosition, scouts, scoutsList, mids, midsList, taken, unexploredList, starPossible, ancientScouts, ancientScoutsList);
			currentPosition = triad[1];
		}
		else // PRZEBUDZENIE MOCY
		{
			// go to closest scout
			path = findPathToClosest(n, neighbours, mids, scouts, currentPosition, 2, ancientScouts);
			
			for (auto it = path.begin(); it != path.end(); ++it)
			{
				feedback = MoveProbe(*it + 1);
				currentPosition = *it;
			}
			
			SafeProbe(n, neighbours, currentPosition, taken, scouts, scoutsList, mids, midsList, unexploredList, ancientScouts, ancientScoutsList);
		}
	}

	return 0;
}