#include <complex>
#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

struct Point;
ostream& operator<<(ostream& os, Point *point);

struct Half {
	Half(Point *m, Point *other) : M(m), Other(other) {
	}

	Point *M;
	Point *Other;
};

struct Point {
	Point(complex<double> z, bool border) : Z(z), Border(border), Visited(false), Index(Counter++) {
	}

	complex<double> Z;
	bool Border;
	bool Visited;
	vector<Half*> Halves;
	vector<Point*> Neighbours;
	int Index;

	Half *Split(Point *other, bool create = true) {
		for (size_t h=0; h<Halves.size(); h++) {
			if (Halves[h]->Other==other) {
				return Halves[h];
			}
		}

		if (create) {
			Point *m = new Point((Z + other->Z)/2., Border && other->Border);

			Half *half = new Half(m, other);
			Halves.push_back(half);

			Half *dual = new Half(m, this);
			other->Halves.push_back(dual);

			return half;
		} else {
			return 0;
		}
	}

	static vector<Point*> JoinFrom;
	static vector<Point*> JoinTo;

	void PostJoin(Point *other) {
		JoinFrom.push_back(this);
		JoinTo.push_back(other);
	}

	void Join(Point *other) {
		if (!Split(other, false)) {
			Neighbours.push_back(other);
			other->Neighbours.push_back(this);

			// complex<double> x = (9.*this->Z + other->Z)/10.;
			// complex<double> y = (this->Z + 9.*other->Z)/10.;

			// cout << "line"
			     // << " @x=" << (int)real(x) << " @y=" << (int)imag(x)
			     // << " @x=" << (int)real(y) << " @y=" << (int)imag(y) << endl;
		}
	}

	static void JoinAll() {
		for (size_t j=0; j<JoinFrom.size(); j++) {
			JoinFrom[j]->Join(JoinTo[j]);
		}
	}

	void Show() {
		cout << (int)real(Z) << " " << (int)imag(Z) << endl;
	}

	static int Counter;
};

vector<Point*> Point::JoinFrom;
vector<Point*> Point::JoinTo;

ostream& operator<<(ostream& os, Point *point) {
	os << " @x=" << (int)real(point->Z) << " @y=" << (int)imag(point->Z);
	return os;
}

//   a-----b
//   |     |
//   |  x..|
//   |  .  |
//   |..v  c-----d
//   |  .     .  |
//   |  y..w..z  |
//   |     .     |
//   f-----------e
Point *first = 0;
void Chair(int i, Point *a, Point *b, Point *c, Point *d, Point *e, Point *f) {
	if (i--) {
		Half *bc = b->Split(c);
		Half *cd = c->Split(d);
		Half *ef = e->Split(f);
		Half *fa = f->Split(a);

		Point *x = new Point((a->Z + c->Z)/2., false);
		Point *y = new Point((f->Z + c->Z)/2., false);
		Point *z = new Point((e->Z + c->Z)/2., false);

		Point *v = x->Split(y)->M;
		Point *w = y->Split(z)->M;

		if (!first) {
			first = y;
		}

		Chair(i, b, bc->M, x, v, fa->M, a);
		Chair(i, x, bc->M, c, cd->M, z, y);
		Chair(i, fa->M, v, y, w, ef->M, f);
		Chair(i, ef->M, w, z, cd->M, d, e);
	} else {
		a->PostJoin(b);
		b->PostJoin(c);
		c->PostJoin(d);
		d->PostJoin(e);
		e->PostJoin(f);
		f->PostJoin(a);

		// a->Show();
		// b->Show();
		// c->Show();
		// d->Show();
		// e->Show();
		// f->Show();
	}
}

int Point::Counter = 0;

void Compute(Point *seed) {
	vector<Point*> current;
	current.push_back(seed);
	seed->Visited = true;

	for (int d=0; current.size(); d++) {
		cout << d << " " << current.size() << endl;

		vector<Point*> after;

		for (size_t c=0; c<current.size(); c++) {
			if (current[c]->Border) {
				return;
			}

			for (size_t n=0; n<current[c]->Neighbours.size(); n++) {
				if (!current[c]->Neighbours[n]->Visited) {
					current[c]->Neighbours[n]->Visited = true;
					after.push_back(current[c]->Neighbours[n]);
				}
			}
		}

		current = after;
	}
}
#define SIZE    1000000
#define DEPTH   11

int main(int argc, const char **argv) {
	//   a-----b
	//   |     |
	//   |  x..|
	//   |  .  |
	//   |...  c-----d
	//   |  .     .  |
	//   |  y.....z  |
	//   |     .     |
	//   f-----------e

	Point *a = new Point(complex<double>(-SIZE, +SIZE), true);
	Point *b = new Point(complex<double>(0,     +SIZE), true);
	Point *c = new Point(complex<double>(0,     0    ), true);
	Point *d = new Point(complex<double>(+SIZE, 0    ), true);
	Point *e = new Point(complex<double>(+SIZE, -SIZE), true);
	Point *f = new Point(complex<double>(-SIZE, -SIZE), true);

	int depth = DEPTH;

	Chair(depth, a, b, c, d, e, f);

	Point::JoinAll();

	cerr << "# got " << Point::Counter << " points at depth " << depth << endl;

	Compute(first);

	return 0;
}