#include <unordered_map>
#include <vector>
#include <cstdio>
#include "gamesa.h"
using namespace std;

struct hrana
{
  unsigned vs[2];

  hrana(void) { vs[0] = vs[1] = 0; }

  hrana(int v1, int v2)
    {
      if (v1 < v2)
	{
	  vs[0] = v1;
	  vs[1] = v2;
	}
      else
	{
	  vs[0] = v2;
	  vs[1] = v1;
	}
    }

  bool operator==(const hrana &s) const
    {
      return vs[0] == s.vs[0] && vs[1] == s.vs[1];
    }
};

static unsigned n;
namespace std {
template <> class hash< hrana > : public unary_function< hrana, size_t >
{
  public:
  size_t operator()(const hrana &h) const
    {
      return h.vs[0] * n + h.vs[1];
    }
};}

// Nezáporná čísla odpovídají vrcholům v cestě (od 0 do n - 3).
// Záporná odpovídají dvojici vrcholů -i - 1 a -i (kde i je od -1 do -(n-3)).
static unordered_map<hrana,int> vceste;
static unordered_map<hrana,bool> obarveny;
static vector<hrana> vrcholy;
static vector<bool> smazany;
static vector<hrana> dvojice;
static bool prvni_tah = true;
static int martah;

static unsigned pred(unsigned k)
{
  return k == 1 ? n : k - 1;
}

static unsigned nasl(unsigned k)
{
  return k == n ? 1 : k + 1;
}

void herni_plan(int inpn, int uhlopricky[][2])
{
  unsigned i, cv;
  int h, d;
  int deg[inpn + 1];

  n = inpn;
  vrcholy.resize(n);
  smazany.resize(n);
  dvojice.resize(n);

  for (i = 0; i < n - 2; i++)
    smazany[i] = false;

  for (i = 1; i <= n; i++)
    deg[i] = 0;

  for (i = 0; i < n - 3; i++)
    {
      deg[uhlopricky[i][0]]++;
      deg[uhlopricky[i][1]]++;
      vceste[hrana(uhlopricky[i][0], uhlopricky[i][1])] = 0;
    };
  for (i = 1; deg[i] > 0; i++)
    continue;

  h = nasl(i);
  d = pred(i);
  vceste[hrana(i, h)] = 0;
  vceste[hrana(i, d)] = 0;
  dvojice[0] = hrana(i, h);
  vrcholy[0] = hrana(i, d);

  for (cv = 1; cv < n - 3; cv++)
    {
      int nh = nasl(h), nd = pred(d);
	  
      vceste[hrana(d, h)] = -cv;
      dvojice[cv] = hrana(d, h);
      if (vceste.count(hrana(d, nh)))
	{
	  vceste[hrana(h, nh)] = cv;
	  vrcholy[cv] = hrana(h, nh);
	  h = nh;
	}
      else
	{
	  vceste[hrana(d, nd)] = cv;
	  vrcholy[cv] = hrana(d, nd);
	  d = nd;
	}
    }

  if (n > 3)
    {
      i = nasl(h);
      vceste[hrana(d, h)] = -cv;
      dvojice[cv] = hrana(d, h);
      vceste[hrana(h, i)] = cv;
      vceste[hrana(d, i)] = cv;
      vrcholy[cv] = hrana(h, i);
      dvojice[cv + 1] = hrana(d, i);
    }
  else
    {
      vceste[hrana(d, h)] = 0;
      dvojice[1] = hrana(d, h);
    }

  for (i = 0; i < n - 2; i++)
    obarveny[vrcholy[i]] = false;
  for (i = 0; i < n - 1; i++)
    obarveny[dvojice[i]] = false;
}

static void zvitezit(int trojuhelnik, int hr[2])
{
  hrana h[3];
  int i;

  h[0] = vrcholy[trojuhelnik];
  h[1] = dvojice[trojuhelnik];
  h[2] = dvojice[trojuhelnik + 1];
  for (i = 0; obarveny[h[i]]; i++)
    continue;

  hr[0] = h[i].vs[0];
  hr[1] = h[i].vs[1];
}

static void tahni(int tah, int hr[2])
{
  hrana h = tah >= 0 ? vrcholy[tah] : dvojice[-tah];
  obarveny[h] = true;

  if (tah >= 0)
    smazany[tah] = true;
  else
    {
      smazany[-tah - 1] = true;
      smazany[-tah] = true;
    }
  hr[0] = h.vs[0];
  hr[1] = h.vs[1];
}

void tah_honzika(int hr[2])
{
  if (prvni_tah)
    {
      if (n % 2 == 0)
	tahni(-((n - 2) / 2), hr);
      else
	tahni((n - 3) / 2, hr);
      prvni_tah = false;
      return;
    }

  if (martah >= 0)
    {
      if (smazany[martah])
	{
	  zvitezit(martah, hr);
	  return;
	}

      smazany[martah] = true;
      tahni(n - 3 - martah, hr);
    }
  else
    {
      if (smazany[-martah - 1])
	{
	  zvitezit(-martah - 1, hr);
	  return;
	}
      if (smazany[-martah])
	{
	  zvitezit(-martah, hr);
	  return;
	}

      smazany[-martah - 1] = true;
      smazany[-martah] = true;
      tahni(-(n - 2) - martah, hr);
    }
}

void tah_marenky(int hr[2])
{
  hrana h(hr[0], hr[1]);
  martah = vceste[h];
  obarveny[h] = true;
}