boolean dfs(int[][] A, int r, int c, boolean[][] b) {
		int n=A.length;
		if (r==n) return true;
		if (c==n) return dfs(A, r+1, 0, b);
		if (A[r][c]!=-1) return dfs(A, r, c+1, b);
		for (int i=0;i<n;++i) 
			if (!b[i][i]&&!b[n+i][i]) {
				b[r][c]=true;
				A[r][c]=i+1;
				if (dfs(A, r, c, b)) return true;
				A[r][c]=-1;
				b[r][c]=false;
			}
		return false;
	}