#include <bits/stdc++.h>
#include "sonlib.h"

using namespace std;

const int N = 405;

bool vis[N];
int edge[N][N];
int par[N];
bool done[N];
int lastEdge[N];
bool examined[N];
int parity;
int n;
set<int> newEdges[N];
int subtask;
int movedTo[N];
int type[N];
int okrazenie[N];
int anyNeigh[N], secondNeigh[N];

int startFrom[N], per[N], whereIs[N];
int remStartFrom[N];

void DFS(int w, vector<int> cycle) {
    //cerr << "w = " << w << endl;
    vis[w] = true;
    
    if (!examined[w]) {
        Examine();
        examined[w] = true;
    }
    
    if (parity == 0) {
        int x = w;
        vector<int> path;
        while (x != cycle[0]) {
            //cerr << x << endl;
            path.push_back(par[x]);
            x = par[x];
        }
        for (int x : path) {
            MoveProbe(x);
        }
        MoveProbe(cycle[1]);
        MoveProbe(cycle[2]);
        MoveProbe(cycle[0]);
        reverse(path.begin(), path.end());
        for (int i = 1; i < path.size(); i++) {
            MoveProbe(path[i]);
        }
        if (path.size() > 0) {
            MoveProbe(w);
        }
        parity = 1 - parity;
    }
    
    for (int u = 1; u <= n; u++) {
        if (w == u) continue;
        edge[w][u] = MoveProbe(u);
        if (edge[w][u] > 0) {
            MoveProbe(w);
        }
    }
    
    for (int u = 1; u <= n; u++) {
        if (edge[w][u] > 0 && !vis[u]) {
            MoveProbe(u);
            parity = 1 - parity;
            par[u] = w;
            DFS(u, cycle);
            MoveProbe(w);
            parity = 1 - parity;
        }
    }
}

// Rozwiazanie ktore aplikuje po znalezieniu cyklu dlugosci 3
void oddCycle(vector<int> cycle) {
    //cerr << "MAMY CYKL" << " " << cycle[0] << " " << cycle[1] << " " << cycle[2] << endl;
    for (int i = 1; i <= n; i++) {
        vis[i] = false;
        par[i] = 0;
    }
    
    // Jestem w cycle[0]
    DFS(cycle[0], cycle);
}

int BFS(int v) {
    for (int i = 1; i <= n; i++) {
        vis[i] = false;
        par[i] = 0;
    }
    queue<int> Q;
    vis[v] = true;
    Q.push(v);
    while (!Q.empty()) {
        int w = Q.front();
        Q.pop();
        if (!done[w]) {
            return w;
        }
        for (int u = 1; u <= n; u++) {
            if (!vis[u] && edge[w][u] > 0) {
                Q.push(u);
                vis[u] = true;
                par[u] = w;
            }
        }
    }
    return -1;
}

int main() {
    srand(531571);
    n = GetN();
    subtask = GetSubtask();
    if (subtask == 2) {
        oddCycle({1, 2, 3});
    }
    
    for (int i = 1; i <= n; i++) {
        startFrom[i] = i;
        per[i] = i;
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            edge[i][j] = -1;
        }
    }
    random_shuffle(startFrom + 1, startFrom + n + 1);
    random_shuffle(per + 1, per + n + 1);
    for (int i = 1; i <= n; i++) {
        whereIs[per[i]] = i;
    }
    
    int parity = 0;
    int w = 1;
    while (true) {
        
        //cerr << "mysle ze jestem w " << w << " " << type[w] << endl;
        if (!examined[w]) {
            //cerr << "egzaminuje w " << endl;
            Examine();
            examined[w] = true;
        }
        
        if (parity == 1) {
            //cerr << "parity 1 " << w << endl;
            if (!done[w]) {
                // Dodaj wszystkie krawedzie
                for (int i = 1; i <= n; i++) {
                    if (w == i) continue;
                    bool res = MoveProbe(i);
//                     if (res)
                    //cerr << "Jest krawedz " << w << " " << i << endl;
//                     else
                        
                    //cerr << "Nie ma krawedzi " << w << " " << i << endl;
                    edge[w][i] = edge[i][w] = res;
                    if (!res) {
                        continue;
                    }
                    MoveProbe(w); // Na pewno sie uda
                }
            }
            done[w] = true;
            
            // Idz do najblizszego nieskonczonego
            
            int u = BFS(w);
            int goal = u;
            //cerr << "Ide do " << u << endl;
            assert(u != -1);
            
            vector<int> path;
            while (u != w) {
                path.push_back(u);
                u = par[u];
            }
            
            reverse(path.begin(), path.end());
            
            for (int u : path) {
                MoveProbe(u); // Powinno sie zawsze udac, bo te krawedzie zostaly juz znalezione
                parity = 1 - parity;
            }
            
            w = goal;
            
            continue;
        }
        
        //cerr << "w " << w << " " << type[w] << endl;
        
        // Zaczynam szukac sasiada
        if (type[w] == 0) {
            
            bool found = false;
            for (int i = 1; i <= n; i++) {
                int starter = startFrom[i];
                int pos = whereIs[starter];
                
                //cerr << "Zaczynamy se z " << per[pos] << endl;
                int nxt = -1;
                for (int steps = 0; steps < n; steps++, pos++) {
                    if (pos > n) pos = 1;
                    int u = per[pos];
                    if (u == w) continue;
                    bool passed = MoveProbe(u);
                    if (passed) {
                        nxt = u;
                        break;
                    }
                }
                if (nxt != -1) { // Istnieje nowa krawedz
                    remStartFrom[w] = starter;
                    movedTo[w] = nxt;
                    type[w] = 1;
                    w = nxt;
                    found = true;
                    break;
                } else {
                    MoveProbe(w);
                }
            }
            
            // Same liscie
            if (!found) {
                for (int i = 1; i <= n; i++) {
                    if (i != w) {
                        MoveProbe(i);
                        Examine();
                        MoveProbe(w);
                    }
                }
                assert(false);
            } else {
                continue;
            }
            
//             newEdges[w].clear();
//             okrazenie[w] = 0;
//             
//             
//             
//             int u = lastEdge[w] + 1;
//             for (int steps = 1; steps < 2 * n; steps++, u++) {
//                 if (u > n) u = 1, okrazenie[w]++;
//                 if (edge[w][u] > 0 || w == u) continue;
//                 bool passed = MoveProbe(u);
//                 if (passed) {
//                     break;
//                 }
//             }
//             if (u != w) { // Istnieje nowa krawedz
//                 movedTo[w] = u;
//                 type[w] = 1;
//                 w = u;
//                 continue;
//             }
            
        } else if (type[w] == 1) { // Znalazlem i weryfikuje
           
            // Sprawdzam cykl dlugosci 3
            
            MoveProbe(movedTo[w]); // Wynik na pewno 0
            int pos = whereIs[remStartFrom[w]];
            bool went = false;
            for (int steps = 0; steps < n; steps++, pos++) {
                if (pos > n) pos = 1;
                int u = per[pos];
//                 //cerr << "u " << u << " " << okr << " " << okrazenie[w] << endl;
                if (u == movedTo[w]) break;
                if (w == u) continue;
                bool passed = MoveProbe(u);
                if (passed) {
                    if (u == movedTo[w]) { // Nie ma krawedzi z w do movedTo[w]
                        break;
                    } else { // Mamy krawedz z w do movedTo[w]
                        went = true;
                        MoveProbe(w); // Odpowiedz na pewno 0, nawet jak jest krawedz
                        bool res = MoveProbe(movedTo[w]);
                        // Jezeli res = 1, to wszedlem tu z w, wiec jest cykl dlugosci 3
                        if (res) {
                            //cerr << "Jest cykl " << movedTo[w] << " " << w << " " << u << endl;
                            oddCycle({movedTo[w], w, u}); // Wazne zeby pierwszy byl movedTo[w], bo tam jestesmy
                        }
                        // Jezeli res = 0, to nie udalo sie zamknac cyklu, wiec siedzimy w movedTo[w] z ta sama parzystoscia i szukamy dalej.
                    }
                }
            }
            //cerr << " elo " << endl;
            int u = per[pos];
            // Nie ma cyklu 3
            assert(u == movedTo[w]);
//             if (!went) {
                MoveProbe(w);
//             } else {}
            
            // Szukam krawedzi, ktora doszedlem do movedTo[w]
            pos = whereIs[remStartFrom[w]];
            for (int steps = 0; steps < n; steps++, pos++) {
                if (pos > n) pos = 1;
                int u = per[pos];
                if (w == u) continue;
                MoveProbe(u); // Wynik zawsze 0
                bool res = MoveProbe(movedTo[w]);
                // Jezeli res, to na pewno istnieje krawedz w-u, a z niej krawedz u-movedTo[w]
                if (res) {
                    break;
                }
            }
            
            u = per[pos];
            MoveProbe(u);
            for (int i = 1; i <= n; i++) {
                //cerr << "TO SIE DZIEJE " << i << endl;
                type[i] = 2;
                //cerr << i << " " << type[i] << endl;
            }
            parity = 1 - parity;
            w = u;
        } else if (type[w] == 2) { // type 2 oznacza ze konczymy zabawe
            //cerr << "JESTEM W " << w << endl;
            assert(parity == 0);
            
            if (anyNeigh[w] == 0) {
                for (int i = 1; i <= n; i++) {
                    if (edge[w][i] > 0) {
                        anyNeigh[w] = i;
                        //cerr << "anyNeigh[w] " << anyNeigh[w] << endl;
                        break;
                    }
                }
                
                for (int i = 1; i <= n; i++) {
                    if (i != w && edge[anyNeigh[w]][i] > 0) {
                        secondNeigh[w] = i;
                        //cerr << "secondNeigh[w] " << secondNeigh[w] << endl;
                        break;
                    }
                }
            }
            
            // Rozpoznajemy wszystkie krawedzie, ktorych nie znamy jednym prostym trickiem.
            
            for (int i = 1; i <= n; i++) {
                //cerr << w << " " << secondNeigh[w] << " " << i << endl;
                if (i == w || edge[w][i] >= 0 || i == secondNeigh[w]) { // Znamy.
                    continue;
                }
                
                //cerr << "sprawdzam " << i << endl;
                MoveProbe(i);
                int res = MoveProbe(secondNeigh[w]);
                // Odpowiedz na pierwsze to zawsze 0. Jesli 
                // na drugie odpowiedz to 1, to znaczy, ze
                // pierwsza krawedz istniala.
                
                if (res) {
                    // Wracam do w.
                    MoveProbe(i);
                    MoveProbe(w);
                    //cerr << "Jest krawedz " << w << " " << i << endl;
                    edge[w][i] = edge[i][w] = true;
                } else {
                    res = MoveProbe(anyNeigh[w]);
                    // Jesli res jest 1, to znaczy ze mamy cykl dlugosci 3 w -> i -> anyNeigh[w] albo w -> anyNeigh[w] -> secondNeigh[w] (gotta check).
                    if (res) {
                        //cerr << "zaszlo" << endl;
//                         oddCycle({anyNeigh[w], w, i});
//                         assert(false);
                        
                        MoveProbe(w);
                        int res = MoveProbe(i);
                        if (!res) { // Przez secondNeigh
                            MoveProbe(anyNeigh[w]);
                            MoveProbe(secondNeigh[w]);
                            MoveProbe(w);
                            edge[w][i] = edge[i][w] = false;
                            
                            //cerr << "Nie ma krawedzi " << w << " " << i << endl        ;
                        } else { // Przez i
                            MoveProbe(anyNeigh[w]);
                            MoveProbe(w);
                            
                            //cerr << "Jest krawedz " << w << " " << i << endl;
                            edge[w][i] = edge[i][w] = true;
                        }
                        continue;
                    } 
                    res = MoveProbe(secondNeigh[w]);
                    // Obserwacja. Jesli jestem w i, to krawedz do secondNeigh nie moze istniec, bo juz to sprawdzilem, wiec res = 0.
                    // Jezeli jestem w anyNeigh[w], to musi byc krawedz do secondNeigh[w], wiec res = 1. 
                    // Nie ma innych opcji.
                    if (res) {
                        //cerr << "Nie ma krawedzi " << w << " " << i << endl;
                        edge[w][i] = edge[i][w] = 0;
                        MoveProbe(anyNeigh[w]);
                        MoveProbe(w);
                    } else {
                        //cerr << "Jest krawedz " << w << " " << i << endl;
                        edge[w][i] = edge[i][w] = 1;
                        MoveProbe(w);
                    }
                }
            }
                
            done[w] = true;
            
            // Idz do najblizszego nieskonczonego
        
            int u = BFS(w);
            int goal = u;
            //cerr << "Ide do " << goal << endl;
            assert(u != -1);
            
            vector<int> path;
            while (u != w) {
                //cerr << "u par[u]" << u << " " << par[u] << endl;
                path.push_back(u);
                u = par[u];
            }
            
            reverse(path.begin(), path.end());
            
            for (int u : path) {
                MoveProbe(u); // Powinno sie zawsze udac, bo te krawedzie zostaly juz znalezione
                parity = 1 - parity;
            }
            w = goal;
        }
    }
    
    return 0;
}