#include <bits/stdc++.h>
#include "code.h"
using namespace std;

vector<pair<int, int>> ZapisiTacke(int N) {
	vector<pair<int, int>> tacke(n+1);
	tacke[0] = {-1,-1};
	for (int i = 0; i<((N+1)/2); i++) {
		tacke[i*2 + 1] = {i+1,0};
	}
	
	for (int i = 0; i<(N/2); i++) {
		tacke[i*2 + 2] = {i+1, 1};
	}
	if ((N&1) == 0) {
		tacke[N] = {N/2+1, 0};
	}
	for (int i = 1; i<=N; i++) {
//		cout << tacke[i].first << ' ' << tacke[i].second << endl;
	}
	
	return tacke;
}

vector<int> Resi(int N, int Q) {
	vector<int> resenje(N+1);

	pair<int,int> kolin = {-1,-1};
	for (int j = 0; j < min(N/2, 3); j++) {
		for (int i = j*2 + 3; i <= N; i++) {
			int res = Pitaj(j*2 + 1,j*2 + 2,i);
			if (res == 0) {
				kolin = {j*2 + 1, j*2 + 2};
				break;
			}
		}
		if (kolin != make_pair(-1,-1)) {
			break;
		}
	}
	if (kolin == make_pair(-1,-1)) {
		if (Pitaj(1,3,5) == 0) {
			kolin = {1,3};
		}
		if (Pitaj(1,3,6) == 0) {
			kolin = {1,3};

		}
		if (Pitaj(1,4,6) == 0) {
			kolin = {1,4};

		}
		if (Pitaj(2,4,6) == 0) {
			kolin = {2,4};

		}
		if (Pitaj(2,4,5) == 0) {
			kolin = {2,4};

		}
		if (Pitaj(2,3,6) == 0) {
			kolin = {2,3};

		}
	}
	vector<pair<int,int>> gore, dole;
	dole.push_back({0,kolin.first});
	dole.push_back({0,kolin.second});
	for (int i = 1; i <= N; i++) {
		if (i == kolin.first || i == kolin.second) {
			continue;
		}
		int res = Pitaj(kolin.first, kolin.second, i);
		if (res == 0) {
			dole.push_back({0,i});
		} else {
			gore.push_back({0,i});
		}
	}
	if (gore.size() > dole.size()) {
		swap(gore, dole);
	}
	int donji = dole[0].second;
	for (int i = 0; i < gore.size(); i++) {
		for (int j = 0; j < gore.size(); j++) {
			if (i==j) {
				continue;
			}
			int res = Pitaj(donji, gore[i].second, gore[j].second);
			gore[i].first += res;
		}
	}
	int gornji = gore[0].second;
	for (int i = 0; i < dole.size(); i++) {
		for (int j = 0; j < dole.size(); j++) {
			if (i==j) {
				continue;
			}
			int res = Pitaj(gornji, dole[i].second, dole[j].second);
			dole[i].first += res;
		}
	}
	sort(gore.begin(), gore.end());
	sort(dole.rbegin(), dole.rend());
	
	vector<int> permutacija(n+1);
	for (int i = 1; i<N; i++) {
		if (i&1) {
			permutacija[i] = dole[i/2].second;
		} else {
			permutacija[i] = gore[i/2 - 1].second;
		}
	}
	permutacija[N] = dole.back().second;
	
	/*for (int i = 0; i < gore.size(); i++) {
		cout << gore[i].first << ' ' << gore[i].second << endl;
	}
	cout << "-----------\n";
	for (int i = 0; i < dole.size(); i++) {
		cout << dole[i].first << ' ' << dole[i].second << endl;
	}
	for (int i = 1; i<=N; i++) {
		cout << permutacija[i] << ' ';
	}
	cout << endl;*/
	return permutacija;
}