#backtracking wrapper, Time O(E^2), Space O(E^2), E is number of edges,
def backtracking(input):
	inputsize = len(input)
	res = []
	makeChain(input, res, inputsize)
	return res
	
# recursive method, Time O(E^2), Space O(E^2)
def makeChain(input, res, inputsize ) :				
    for  i in range(0, len(input)):
        dom = input[i]
        if len(res) == 0 or res[len(res)-1][1] == dom[0] : #check whether they can be chained
            res.append(dom)
            if (len(res) == inputsize) : # reach the length, stop 	
                return;	            	
            saved = input.pop(i); # remove at i
            makeChain(input, res, inputsize)
            input.insert(i, saved)  # backtracking, insert at index
            res.pop(len(res)-1)  #remove last
        dom = [dom[1], dom[0]] #reverse, both way
        if len(res) == 0 or res[len(res)-1][1] == dom[0] :
            res.append(dom)
            if (len(res) == inputsize) :		            	   
                return
            saved = input.pop(i); #remove at i
            makeChain(input, res, inputsize)
            input.insert(i, saved); #backtracking, add at i
            res.pop(len(res)-1)
	
# print, Time O(E), Space O(1)
def printChain(chain) :	
	for i in range(0, len(chain)): 
		print("["+str(chain[i][0]) +", " + str(chain[i][1])+"] ", end=' ' )
	print()

input = []
input.append([3, 1])
input.append([2, 1])
input.append([1, 3])
input.append([2, 2])
input.append([1, 2])
print("input:")
printChain(input)
output = backtracking(input)
print("Backtracking:")
printChain(output)