import copy

# permutations
U_move = [ [ [1, 0, 0], [4, 0, 0], [3, 0, 0], [2, 0, 0] ], [ [1, 0, 1], [4, 0, 1], [3, 0, 1], [2, 0, 1] ], [ [1, 0, 2], [4, 0, 2], [3, 0, 2], [2, 0, 2] ], [[0, 0, 0], [0, 0, 2], [0, 2, 2], [0, 2, 0]], [[0, 0, 1], [0, 1, 2], [0, 2, 1], [0, 1, 0]] ]
L_move = [ [ [0, 0, 0], [2, 0, 0], [5, 0, 0], [4, 2, 2] ], [ [0, 1, 0], [2, 1, 0], [5, 1, 0], [4, 1, 2] ], [ [0, 2, 0], [2, 2, 0], [5, 2, 0], [4, 0, 2] ], [[1, 0, 0], [1, 0, 2], [1, 2, 2], [1, 2, 0]], [[1, 0, 1], [1, 1, 2], [1, 2, 1], [1, 1, 0]] ]
F_move = [ [ [0, 2, 0], [3, 0, 0], [5, 0, 2], [1, 2, 2] ], [ [0, 2, 1], [3, 1, 0], [5, 0, 1], [1, 1, 2] ], [ [0, 2, 2], [3, 2, 0], [5, 0, 0], [1, 0, 2] ], [[2, 0, 0], [2, 0, 2], [2, 2, 2], [2, 2, 0]], [[2, 0, 1], [2, 1, 2], [2, 2, 1], [2, 1, 0]] ]
R_move = [ [ [0, 2, 2], [4, 0, 0], [5, 2, 2], [2, 2, 2] ], [ [0, 1, 2], [4, 1, 0], [5, 1, 2], [2, 1, 2] ], [ [0, 0, 2], [4, 2, 0], [5, 0, 2], [2, 0, 2] ], [[3, 0, 0], [3, 0, 2], [3, 2, 2], [3, 2, 0]], [[3, 0, 1], [3, 1, 2], [3, 2, 1], [3, 1, 0]] ]
B_move = [ [ [0, 0, 2], [1, 0, 0], [5, 2, 0], [3, 2, 2] ], [ [0, 0, 1], [1, 1, 0], [5, 2, 1], [3, 1, 2] ], [ [0, 0, 0], [1, 2, 0], [5, 2, 2], [3, 0, 2] ], [[4, 0, 0], [4, 0, 2], [4, 2, 2], [4, 2, 0]], [[4, 0, 1], [4, 1, 2], [4, 2, 1], [4, 1, 0]] ]
D_move = [ [ [2, 2, 0], [3, 2, 0], [4, 2, 0], [1, 2, 0] ], [ [2, 2, 1], [3, 2, 1], [4, 2, 1], [1, 2, 1] ], [ [2, 2, 2], [3, 2, 2], [4, 2, 2], [1, 2, 2] ], [[5, 0, 0], [5, 0, 2], [5, 2, 2], [5, 2, 0]], [[5, 0, 1], [5, 1, 2], [5, 2, 1], [5, 1, 0]] ]

#   0             U
# 1 2 3 4       L F R B
#   5             D

moves = ["U", "U2", "U'", "L", "L'", "L2", "F", "F'", "F2", "R", "R'", "R2", "B", "B'", "B2", "D", "D'", "D2"]

class Rubik:
	"""The cube."""

	def __init__(self):

		self.reset()
		self.save() # previous is a independent copy of the cube. This is helpful in bruteforce.

	def reset(self, cube = None):
		"""Resets cube to solved one or given status."""

		if cube:
			self.cube = copy.deepcopy(cube) # independent copy of the given list. Helpful in bruteforce.

		else:
			self.cube =	[	[["W", "W", "W"], ["W", "W", "W"], ["W", "W", "W"]], # six faces, in each face a 3x3 matrix.
							[["O", "O", "O"], ["O", "O", "O"], ["O", "O", "O"]],
							[["G", "G", "G"], ["G", "G", "G"], ["G", "G", "G"]],
							[["R", "R", "R"], ["R", "R", "R"], ["R", "R", "R"]],
							[["B", "B", "B"], ["B", "B", "B"], ["B", "B", "B"]],
							[["Y", "Y", "Y"], ["Y", "Y", "Y"], ["Y", "Y", "Y"]] ]

	def move_perm(self, perm, d=1):
		"""Moves the cube given a permutation of pieces."""

		for x in perm:
			temp = []
			for y in x: temp.append( self.cube[y[0]][y[1]][y[2]] )
			for j in xrange(len(x)): self.cube[x[j][0]][x[j][1]][x[j][2]] = temp[j-d]

	def move(self, face):
		"""Moves a face of the cube."""

		d = 1
		if face[-1] == "'": d = 3
		elif face[-1] == "2": d = 2

		if face[0] == "U": self.move_perm(U_move, d)
		elif face[0] == "L": self.move_perm(L_move, d)
		elif face[0] == "F": self.move_perm(F_move, d)
		elif face[0] == "R": self.move_perm(R_move, d)
		elif face[0] == "B": self.move_perm(B_move, d)
		elif face[0] == "D": self.move_perm(D_move, d)

	def move_sequence(self, sequence):
		"""Performs moves given a sequence of turns. Like scramble."""

		for turn in sequence.split(): self.move(turn)

	def face_solved(self, nro):
		"""Checks if the face nro of the cube is solved."""
		a = self.cube[nro][0][0]

		for i in xrange(3):
			for j in xrange(3):
				if self.cube[nro][i][j] != a:
					return False

		return True

	def is_solved(self):
		"""Checks if a cube is solved."""

		for i in xrange(6):
			if not self.face_solved(i): return False

		return True

	def save(self):
		self.previous = copy.deepcopy(self.cube)

def same(move1, move2):
	"""Checks if two moves are of the same type. This is to avoid sequences like "U U2" or "D' D"."""

	return move1[0] == move2[0]

def intersection(move1, move2):
	"""Returns true if move1 and move2 intersects and false if they don't. This is to avoid sequence like "U D U" or "F B' F2."""

	x = move1[0]
	y = move2[0]

	if x in "UD": return y not in "UD"
	elif x in "LR": return y not in "LR"
	elif x in "FB": return y not in "FB"

	return False

def count_cycle(com):

	cubo=Rubik()

	c=0
	while 1:
		cubo.move_sequence(com)
		c+=1
		if cubo.is_solved(): break
	return max(1,c)

def increment(seq, pos = None, mov = moves):
	"""Brute force for movements."""

	if pos is None:
		pos = len(seq)-1

	seq[pos] += 1

	if seq[pos] == len(mov):
		seq[pos] = 0

		if pos == 0:
			seq.append(0)
			print "Size", len(seq) # control how much moves we have

		else: increment(seq, pos-1, mov)

		check(seq, mov)

def check(seq, mov = moves):

	for i in xrange(len(seq) - 1):

		if same(mov[seq[i]], mov[seq[i+1]]) or (len(seq)>2 and i>0 and (not intersection(mov[seq[i-1]], mov[seq[i]]) and not intersection(mov[seq[i]], mov[seq[i+1]])) ): # consecutives moves are of the same type, like U' U2.

			increment(seq, i+1, mov) # increments the next one

			j = i+2
			while j < len(seq):
				seq[j] = 0 # zeroes to the rest to begin again
				j += 1

			if j>i+2: check(seq, mov) # if zero at some part, check the rest of the sequence

			break # as the rest of the sequence is checked, there's no need to continue with i

def main():

	maximo = 0
	result = ""

	possible_cycles = [0, 1] #lazy way to avoid some moves. this explais the [2:] below
	corresponding_sequences = ["", ""]

	temp = [0]

	while 1:

		sequence = []

		for x in temp: sequence.append(moves[x]) # prints the sequence that leads to 2x2x2 block

		seq = " ".join(sequence)

		cycle = count_cycle(seq)

		if cycle not in possible_cycles:
			possible_cycles.append(cycle)
			corresponding_sequences.append(seq)

			print cycle, "-", seq

		increment(temp)
		while temp[0] > 1: # cheat. always start with U or U2 moves.
			increment(temp)

main()