import java.util.*;
public class FindDominosChain {
	
	//backtracking wrapper, Time O(E^2), Space O(E^2), E is number of edges,
	public static ArrayList<int[]> backtracking(ArrayList<int[]> input) {
		int inputsize = input.size();
		ArrayList<int[]> res = new ArrayList<>();
	    makeChain(input, res, inputsize);
	    return res;
	}
	
    // recursive method, Time O(E^2), Space O(E^2)
	private static void makeChain(ArrayList<int[]> input, ArrayList<int[]> res, int inputsize) {				
	    for (int i = 0; i < input.size(); i++) {
	    	int[] dom = input.get(i);
	        if (res.isEmpty() || res.get(res.size()-1)[1] == dom[0]) { //check whether they can be chained
	        	res.add(dom);
		        if (res.size() == inputsize) { //reach the length
		        		return;	            	
		        }
		        int[] saved = input.remove(i);
	            makeChain(input, res, inputsize);
	            input.add(i, saved);  //backtracking
	            res.remove(res.size()-1);
	        }
	        dom = new int[]{dom[1], dom[0]}; //reverse, both way
	        if (res.isEmpty() || res.get(res.size()-1)[1] == dom[0]) {
	            res.add(dom);
		        if (res.size() == inputsize) {	
		        		return;
		        }
		        int[] saved = input.remove(i);
	            makeChain(input, res, inputsize);
	            input.add(i, saved); //backtracking
	            res.remove(res.size()-1);
	        }
	    }
	}
	//Time O(E) Space O(1)
	private static void printChain(List<int[]> chain){		
		for (int i = 0; i<chain.size();i++) 
			System.out.print("["+chain.get(i)[0]+", " + chain.get(i)[1]+"] " );
		System.out.println(); 
	}

	public static void main(String... args) {
	    ArrayList<int[]> input = new ArrayList<>();
	    input.add(new int[]{1,1});
		input.add(new int[]{3,1});
		input.add(new int[]{2,1});
		input.add(new int[]{1,3});
		input.add(new int[]{2,2});
		input.add(new int[]{1,2});
		System.out.println("input:");
		printChain(input);
	    ArrayList<int[]> output = backtracking(input);
	    System.out.println("backtracking:");
	    printChain(output);
	    
	}    
}