#include <stdio.h>	/* fclose(), fopen(), fprintf() */
#include <string.h>	/* memcpy(), memset() */

typedef struct {
	int path, length;
} FaceType;

typedef struct {
	int length_total;
	FaceType face_list[10];	/* 1-4 are repeated at the end */
} CornerType;

typedef struct {
	int corners, max_length;
	CornerType corner_list[6];
} CubeType;

CubeType cubes[8] = {
	{ 5, 6, {	/* #1 */
	    {6,{{1,3},{1,3},{2,2},{3,1},{3,1},{2,2},{1,3},{1,3},{2,2},{3,1}}},
	    {4,{{0,0},{1,4},{1,4},{0,0},{0,0},{0,0},{0,0},{1,4},{1,4},{0,0}}},
	    {4,{{1,2},{2,2},{1,2},{2,2},{0,0},{0,0},{1,2},{2,2},{1,2},{2,2}}},
	    {4,{{1,2},{2,2},{1,2},{0,0},{2,2},{0,0},{1,2},{2,2},{1,2},{0,0}}},
	    {3,{{1,1},{2,1},{2,1},{3,1},{3,1},{1,1},{1,1},{2,1},{2,1},{3,1}}},
	    {0,{{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}}}
	} },
	{ 4, 4, {	/* #2 */
	    {4,{{1,2},{2,2},{1,2},{2,2},{0,0},{0,0},{1,2},{2,2},{1,2},{2,2}}},
	    {3,{{1,3},{0,0},{1,3},{0,0},{0,0},{0,0},{1,3},{0,0},{1,3},{0,0}}},
	    {2,{{1,2},{1,2},{0,0},{0,0},{0,0},{0,0},{1,2},{1,2},{0,0},{0,0}}},
	    {2,{{0,0},{1,1},{1,1},{2,1},{2,1},{0,0},{0,0},{1,1},{1,1},{2,1}}},
	    {0,{{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}}},
	    {0,{{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}}}
	} },
	{ 5, 6, {	/* #3 */
	    {6,{{1,3},{1,3},{2,2},{3,1},{3,1},{2,2},{1,3},{1,3},{2,2},{3,1}}},
	    {4,{{1,2},{2,2},{1,2},{2,2},{0,0},{0,0},{1,2},{2,2},{1,2},{2,2}}},
	    {4,{{1,2},{2,2},{1,2},{0,0},{2,2},{0,0},{1,2},{2,2},{1,2},{0,0}}},
	    {4,{{1,2},{1,2},{2,2},{0,0},{2,2},{0,0},{1,2},{1,2},{2,2},{0,0}}},
	    {2,{{0,0},{1,1},{1,1},{2,1},{2,1},{0,0},{0,0},{1,1},{1,1},{2,1}}},
	    {0,{{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}}}
	} },
	{ 3, 4, {	/* #4 */
	    {4,{{1,3},{2,1},{2,1},{1,3},{0,0},{0,0},{1,3},{2,1},{2,1},{1,3}}},
	    {2,{{1,2},{1,2},{0,0},{0,0},{0,0},{0,0},{1,2},{1,2},{0,0},{0,0}}},
	    {2,{{0,0},{1,1},{1,1},{2,1},{2,1},{0,0},{0,0},{1,1},{1,1},{2,1}}},
	    {0,{{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}}},
	    {0,{{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}}},
	    {0,{{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}}}
	} },
	{ 5, 6, {	/* #5 */
	    {6,{{1,2},{2,2},{3,2},{3,2},{1,2},{2,2},{1,2},{2,2},{3,2},{3,2}}},
	    {6,{{1,3},{1,3},{2,2},{3,1},{3,1},{2,2},{1,3},{1,3},{2,2},{3,1}}},
	    {4,{{1,2},{2,2},{1,2},{2,2},{0,0},{0,0},{1,2},{2,2},{1,2},{2,2}}},
	    {3,{{1,2},{2,1},{2,1},{0,0},{1,2},{0,0},{1,2},{2,1},{2,1},{0,0}}},
	    {3,{{1,1},{2,1},{2,1},{3,1},{3,1},{1,1},{1,1},{2,1},{2,1},{3,1}}},
	    {0,{{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}}}
	} },
	{ 4, 4, {	/* #6 */
	    {4,{{1,3},{2,1},{2,1},{0,0},{1,3},{0,0},{1,3},{2,1},{2,1},{0,0}}},
	    {4,{{1,2},{1,2},{2,2},{0,0},{2,2},{0,0},{1,2},{1,2},{2,2},{0,0}}},
	    {3,{{1,1},{2,2},{0,0},{2,2},{0,0},{1,1},{1,1},{2,2},{0,0},{2,2}}},
	    {2,{{0,0},{1,1},{1,1},{2,1},{2,1},{0,0},{0,0},{1,1},{1,1},{2,1}}},
	    {0,{{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}}},
	    {0,{{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}}}
	} },
	{ 6, 5, {	/* #7 */
	    {5,{{0,0},{1,2},{2,3},{2,3},{1,2},{0,0},{0,0},{1,2},{2,3},{2,3}}},
	    {4,{{1,2},{2,2},{1,2},{0,0},{2,2},{0,0},{1,2},{2,2},{1,2},{0,0}}},
	    {4,{{1,2},{2,2},{0,0},{1,2},{0,0},{2,2},{1,2},{2,2},{0,0},{1,2}}},
	    {3,{{1,3},{0,0},{1,3},{0,0},{0,0},{0,0},{1,3},{0,0},{1,3},{0,0}}},
	    {3,{{1,2},{2,1},{2,1},{1,2},{0,0},{0,0},{1,2},{2,1},{2,1},{1,2}}},
	    {3,{{1,1},{2,2},{0,0},{2,2},{0,0},{1,1},{1,1},{2,2},{0,0},{2,2}}}
	} },
	{ 4, 6, {	/* #8 */
	    {6,{{1,2},{2,2},{3,2},{1,2},{2,2},{3,2},{1,2},{2,2},{3,2},{1,2}}},
	    {5,{{0,0},{1,2},{2,3},{2,3},{1,2},{0,0},{0,0},{1,2},{2,3},{2,3}}},
	    {4,{{1,2},{0,0},{2,2},{1,2},{2,2},{0,0},{1,2},{0,0},{2,2},{1,2}}},
	    {3,{{1,2},{2,1},{2,1},{1,2},{0,0},{0,0},{1,2},{2,1},{2,1},{1,2}}},
	    {0,{{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}}},
	    {0,{{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}}}
	} }
};


CubeType *cube_list[8];
CornerType *corner_list[8];
FaceType *face_list[8];
int path_list[8][4];
int current_max_length;

int min_length;
#define MAX_LENGTH 41

int path_length[25];
int match[25][25];	/* has to be symmetric for sum_path() to work */
int max_path_number;
int paths[8][4];

void print_result() {
	int i;
	FILE *fout = fopen("third.out", "a");
	fprintf(fout, "%2d ", min_length);
	for (i = 0; i < 8; i++) {
		fprintf(fout, "%d", cube_list[i] - cubes);
	}
	fprintf(fout, " ");
	for (i = 0; i < 8; i++) {
		fprintf(fout, "%d", corner_list[i] - cube_list[i]->corner_list);
	}
	fprintf(fout, " ");
	for (i = 0; i < 8; i++) {
		fprintf(fout, "%d", (face_list[i] - corner_list[i]->face_list) / 2);
	}
	fprintf(fout, "\n");
	fclose(fout);
}

void sum_path() {
	int i, j, k;
	int best_path = -1;
	for (i = 1; i <= max_path_number; i++) {
		if (path_length[i] != -1) {
			for (j = i + 1; j <= max_path_number; j++) {
				int new_j = 0;
				if (match[i][j] && path_length[j] != -1) {
					for (k = i + 1; k <= max_path_number; k++) {
						if (match[j][k]) {
							match[i][k] = 1;
							if (!new_j && k < j) {
								new_j = k - 1;
							}
						}
					}
					if (path_length[j]) {
						path_length[i] += path_length[j];
					} else {
						path_length[i] = 0;
					}
					path_length[j] = -1;
				}
				if (new_j) {
					j = new_j;
				}
			}
			if (path_length[i] > best_path) {
				best_path = path_length[i];
			}
		}
	}
	if (best_path >= min_length) {
		min_length = best_path;
		print_result();
	}
}

void face_check(FaceType *a0, FaceType *a1, int i0, int i1) {
	if (a0->path && a1->path) {
		int *p0 = paths[i0] + a0->path;
		int *p1 = paths[i1] + a1->path;
		if (*p0) {
			if (*p1) {
				match[*p0][*p1] = match[*p1][*p0] = 1;
			} else {
				path_length[*p1 = *p0] += a1->length;
			}
		} else if (*p1) {
			path_length[*p0 = *p1] += a0->length;
		} else {
			*p0 = *p1 = ++max_path_number;
			path_length[max_path_number] = a0->length + a1->length;
		}
	}
}

void add_face(int i0) {			/* only works for faces 0, 3, 5, 6 */
	int i1 = i0 + (i0 & 2 ? -2 : 2);
	int i2 = i0 + (i0 & 4 ? -4 : 4);
	int i3 = i0 + (i0 & 1 ? -1 : 1);
	FaceType *a0 = face_list[i0];
	FaceType *a1 = face_list[i1];
	FaceType *a2 = face_list[i2];
	FaceType *a3 = face_list[i3];
	face_check(a0    , a1 + 5, i0, i1);
	face_check(a0 + 1, a1 + 4, i0, i1);
	face_check(a0 + 2, a2 + 3, i0, i2);
	face_check(a0 + 3, a2 + 2, i0, i2);
	face_check(a0 + 4, a3 + 1, i0, i3);
	face_check(a0 + 5, a3    , i0, i3);
}

void face_check2(FaceType *a0, FaceType *a1, int i0, int i1) {
	if (a0->path && !a1->path) {
		int *p0 = paths[i0] + a0->path;
		if (*p0) {
			path_length[*p0] = 0;
			*p0 = 0;
		}
	} else if (!a0->path && a1->path) {
		int *p1 = paths[i1] + a1->path;
		if (*p1) {
			path_length[*p1] = 0;
			*p1 = 0;
		}
	}
}

void subtract_face(int i0) {		/* only works for faces 0, 3, 5, 6 */
	int i1 = i0 + (i0 & 2 ? -2 : 2);
	int i2 = i0 + (i0 & 4 ? -4 : 4);
	int i3 = i0 + (i0 & 1 ? -1 : 1);
	FaceType *a0 = face_list[i0];
	FaceType *a1 = face_list[i1];
	FaceType *a2 = face_list[i2];
	FaceType *a3 = face_list[i3];
	face_check2(a0    , a1 + 5, i0, i1);
	face_check2(a0 + 1, a1 + 4, i0, i1);
	face_check2(a0 + 2, a2 + 3, i0, i2);
	face_check2(a0 + 3, a2 + 2, i0, i2);
	face_check2(a0 + 4, a3 + 1, i0, i3);
	face_check2(a0 + 5, a3    , i0, i3);
}

void detailed_check() {
	max_path_number = 0;
	memset(match, 0, sizeof(match));
	memset(paths, 0, sizeof(paths));
	add_face(0);
	add_face(3);
	add_face(5);
	add_face(6);
	subtract_face(0);
	subtract_face(3);
	subtract_face(5);
	subtract_face(6);
	sum_path();
}

void spin_check(int cube) {		/* only works for cube = 1, 2, 4, 7 */
	CornerType *b = corner_list[cube];
	FaceType *a0 = b->face_list;
	FaceType *end = a0 + 6;
	int i1 = cube + (cube & 1 ? -1 : 1);
	int i2 = cube + (cube & 4 ? -4 : 4);
	int i3 = cube + (cube & 2 ? -2 : 2);
	FaceType *a1 = face_list[i1];
	FaceType *a2 = face_list[i2];
	FaceType *a3 = face_list[i3];
	int r0, r1, r2, r3, r4, r5;	/* reset path_list for given face */
	int local_path_list[4];
	int save_current_max_length = current_max_length;
	r0 = r1 = r2 = r3 = r4 = r5 = 0;
	for (; a0 < end; a0 += 2) {
		int lost = 0;
		memset(local_path_list, 0, sizeof(local_path_list));
		if (!a0[0].path && a1[5].path && !path_list[i1][a1[5].path]) {
			r0 = 1;
			lost += a1[5].length;
			path_list[i1][a1[5].path]++;
		}
		if (!a0[1].path && a1[4].path && !path_list[i1][a1[4].path]) {
			r1 = 1;
			lost += a1[4].length;
			path_list[i1][a1[4].path]++;
		}
		if (!a0[2].path && a2[3].path && !path_list[i2][a2[3].path]) {
			r2 = 1;
			lost += a2[3].length;
			path_list[i2][a2[3].path]++;
		}
		if (!a0[3].path && a2[2].path && !path_list[i2][a2[2].path]) {
			r3 = 1;
			lost += a2[2].length;
			path_list[i2][a2[2].path]++;
		}
		if (!a0[4].path && a3[1].path && !path_list[i3][a3[1].path]) {
			r4 = 1;
			lost += a3[1].length;
			path_list[i3][a3[1].path]++;
		}
		if (!a0[5].path && a3[0].path && !path_list[i3][a3[0].path]) {
			r5 = 1;
			lost += a3[0].length;
			path_list[i3][a3[0].path]++;
		}
		if (a0[0].path && !a1[5].path && !local_path_list[a0[0].path]) {
			lost += a0[0].length;
			local_path_list[a0[0].path] = 1;
		}
		if (a0[1].path && !a1[4].path && !local_path_list[a0[1].path]) {
			lost += a0[1].length;
			local_path_list[a0[1].path] = 1;
		}
		if (a0[2].path && !a2[3].path && !local_path_list[a0[2].path]) {
			lost += a0[2].length;
			local_path_list[a0[2].path] = 1;
		}
		if (a0[3].path && !a2[2].path && !local_path_list[a0[3].path]) {
			lost += a0[3].length;
			local_path_list[a0[3].path] = 1;
		}
		if (a0[4].path && !a3[1].path && !local_path_list[a0[4].path]) {
			lost += a0[4].length;
			local_path_list[a0[4].path] = 1;
		}
		if (a0[5].path && !a3[0].path && !local_path_list[a0[5].path]) {
			lost += a0[5].length;
			local_path_list[a0[5].path] = 1;
		}
		if (current_max_length >= min_length + lost) {
			current_max_length -= lost;
			face_list[cube] = a0;
			switch (cube) {
				case 1:
					spin_check(2);
					break;
				case 2:
					spin_check(4);
					break;
				case 4:
					spin_check(7);
					break;
				case 7:
					detailed_check();
			}
			current_max_length = save_current_max_length;
		}
		if (r0) {
			r0 = 0;
			path_list[i1][a1[5].path]--;
		}
		if (r1) {
			r1 = 0;
			path_list[i1][a1[4].path]--;
		}
		if (r2) {
			r2 = 0;
			path_list[i2][a2[3].path]--;
		}
		if (r3) {
			r3 = 0;
			path_list[i2][a2[2].path]--;
		}
		if (r4) {
			r4 = 0;
			path_list[i3][a3[1].path]--;
		}
		if (r5) {
			r5 = 0;
			path_list[i3][a3[0].path]--;
		}
	}
}

void spin() {
	FaceType *a3, *a5, *a6;
	FaceType *end3 = corner_list[3]->face_list + 6;
	FaceType *end5 = corner_list[5]->face_list + 6;
	FaceType *end6 = corner_list[6]->face_list + 6;
	face_list[0] = corner_list[0]->face_list;
	for (a3 = end3 - 6; a3 < end3; a3 += 2) {
		face_list[3] = a3;
		for (a5 = end5 - 6; a5 < end5; a5 += 2) {
			face_list[5] = a5;
			for (a6 = end6 - 6; a6 < end6; a6 += 2) {
				face_list[6] = a6;
				memset(path_list, 0, sizeof(path_list));
				spin_check(1);
			}
		}
	}
}

void corner(int cube) {
	CubeType *b = cube_list[cube];
	CornerType *a = b->corner_list;
	CornerType *end = a + b->corners;
	int max_length = current_max_length - b->max_length;
	for (; a < end; a++) {
		current_max_length = max_length + a->length_total;
		if (current_max_length >= min_length) {
			corner_list[cube] = a;
			if (cube < 7) {
				corner(cube + 1);
			} else {
				spin();
			}
		}
	}
}

void poly(int level, CubeType *left[]) {
	if (level < 7) {
		int i;
		CubeType *now_left[8];
		for (i = 0; i < 8 - level; i++) {
			cube_list[level] = left[i];
			if (i) {
				memcpy(now_left, left, i * sizeof(CubeType *));
			}
			if (i < 7 - level) {
				memcpy(now_left + i, left + i + 1, (7 - level - i) * sizeof(CubeType *));
			}
			poly(level + 1, now_left);
		}
	} else {
		cube_list[7] = left[0];
		current_max_length = MAX_LENGTH;
		corner(0);
	}
}

int main() {
	int i;
	CubeType *starting[8];
	FILE *fout = fopen("third.out", "w");
	fclose(fout);
	for (i = 0; i < 7; i++) {
		starting[i] = cubes + i + 1;
	}
	cube_list[0] = cubes;
	min_length = -1;
	poly(1, starting); 
	return 0;
}