public static int coloringNumber(int n) {
		if (n<=1) return 1;
		int[][]dp=new int[4][n];
		// 0  :  0  0 
		// 1  :  0  1
		// 2  :  1  0
		// 3  :  1  1
		for (int i=0;i<4;++i) dp[i][1]=1;
		for (int j=2;j<n;++j) {
			dp[0][j]=dp[2][j-1];
			dp[1][j]=dp[0][j-1]+dp[2][j-1];
			dp[2][j]=dp[1][j-1]+dp[3][j-1];
			dp[3][j]=dp[1][j-1];
		}
		int rel=0;
		for (int i=0;i<4;++i)rel+=dp[i][n-1];
		return rel;
	}