1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include "bits/stdc++.h"
#include "sonlib.h"

using namespace std;

int main() {
  int n = GetN();
  int last_result = -1;
  auto MyMoveProbe = [&](int v) {
    #ifdef LOCAL
      cerr << "Try to move to " << v << "\n";
    #endif
    last_result = MoveProbe(v+1);
    #ifdef LOCAL
      cerr << "Current node: " << GetCurrentNode() << "\n";
    #endif
    return last_result;
  };
  auto MyMoveProbeV = [&](vector <int> V) {
    for (auto v : V) MyMoveProbe(v);
  };
  auto find_edge = [&] {
    // for (int st=0; st<n; st++) {
    //   vector <int> trip;
    //   for (int roz = 0; roz < n-1; roz++) {
    //     if (roz % 2 == 0) trip.push_back((st-roz+n)%n);
    //     else trip.push_back((st+roz)%n);
    //   }
    //   for (int i=1; i<(int)trip.size(); i++) {
    //     if (MyMoveProbe(trip[i])) {
    //       return vector<int>(trip.begin(), trip.begin()+i+1);
    //     }
    //   }
    //   if(st + 1 < n) MyMoveProbe(st + 1);
    // }
    vector <int> trip;
    for (int i=0; i<n; i++) trip.push_back(i);
    for (int i=1; i<n; i++) {
      for (int j=1; j<(int)trip.size(); j++) {
        if (MyMoveProbe(trip[j])) {
          return vector<int>(trip.begin(), trip.begin()+j+1);
        }
      }
      rotate(trip.begin()+1, trip.begin()+2, trip.end());
      MyMoveProbe(0);
    }
    for (int i=1; i<n; i++) {
      MyMoveProbe(i);
      Examine();
      MyMoveProbe(0);
    }
    Examine();
    exit(0);
  };
  auto path = find_edge();
  int st = path.front(), ko = path.back();
  path.pop_back();
  path.erase(path.begin());
  auto find_closer_neighbour = [&] {
    for (int i=0; i<(int)path.size(); i++) {
      if (MyMoveProbe(path[i])) {
        st = ko;
        ko = path[i];
        path.resize(i);
        return true;
      }
    }
    return false;
  };
  auto shorten_path = [&] {
    while ((int)path.size() != 1) {
      if (!find_closer_neighbour()) {
        MyMoveProbe(ko);
        int first = path.front();
        path.erase(path.begin());
        MyMoveProbe(first);
        if (MyMoveProbe(st)) {
          return vector<int>{ko, first, st};
        }
        for (auto p : path) {
          if (MyMoveProbe(p)) {
            return vector<int>{ko, st, p};
          }
        }
        MyMoveProbe(ko);
      }
    }
    return vector<int>{st, path[0], ko};
  };
  auto two_edges = shorten_path();
  assert(two_edges.size() == 3);
  #ifdef LOCAL
    int pa = two_edges[0], pb = two_edges[1], pc = two_edges[2];
    cerr << pa << " " << pb << " " << pc << "\n";
    assert(CheckEdge(pa, pb));
    assert(CheckEdge(pb, pc));
    cerr << GetCurrentNode() << "\n";
    assert(GetCurrentNode() == pc);
  #endif
  vector <int> current_path = two_edges;
  reverse(two_edges.begin(), two_edges.end());
  set <int> remaining;
  for (int i=0; i<n; i++) remaining.insert(i);
  for (int i=0; i<3; i++) remaining.erase(two_edges[i]);
  function<void(int)> explore = [&](int cur) {
    Examine();
    for (int i=0; i<n; i++) {
      if (remaining.find(i) == remaining.end()) continue;
      bool edge_exists = false, changed_parity = false;
      int last2 = current_path[current_path.size()-2],
          last3 = current_path[current_path.size()-3];
      if (last_result) {
        MyMoveProbe(last3);
        if (!MyMoveProbe(last2)) {
          MyMoveProbeV({cur,i});
          edge_exists = true;
          if (MyMoveProbe(last3) or MyMoveProbe(last2)) {
            MyMoveProbe(i);
          } else if (MyMoveProbe(last3)) {
            MyMoveProbe(last2);
            edge_exists = false;
          }
        } else {
          changed_parity = true;
        }
        MyMoveProbe(cur);
      }
      if (last_result == false or edge_exists) {
        if (MyMoveProbe(i) or edge_exists) {
          remaining.erase(i);
          current_path.push_back(i);
          explore(i);
          current_path.pop_back();
          MyMoveProbe(cur);
        }
      }
      if (changed_parity) {
        MyMoveProbeV({last3,last2,cur});
      }
    }
  };
  for (int i=0; i<3; i++) {
    explore(two_edges[i]);
    MyMoveProbe(two_edges[(i+1)%3]);
    current_path.push_back(two_edges[(i+1)%3]);
  }
  assert(false);  // :(
}