🧩 N-Queen (Special)

N-Queen 문제는 크기가 $N \times N$인 체스판 위에 퀸 $N$개를 서로 공격할 수 없게 놓는 문제이다.

$N$이 주어졌을 때, 퀸을 놓는 방법 한 가지를 출력하는 것은 쉽다.

이 문제에서는 몇 개의 퀸이 이미 놓여있을 때, 퀸을 놓는 방법 한 가지를 출력해 보자.

첫 번째 줄에 $N$과 이미 놓여있는 퀸의 개수 $Q$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $Q$개의 줄에 걸쳐 이미 놓여있는 퀸의 위치가 주어진다. 그중 $i$번째 줄에는 $i$번째 퀸의 행의 번호 $r\_i$, 열의 번호 $c\_i$이 공백으로 구분되어 주어진다. $(1 \le r\_i, c\_i \le N)$

같은 좌표에 $2$개 이상의 퀸이 주어지는 입력은 없다. 퀸이 서로 공격하는 올바르지 않은 상태의 입력 혹은 $N$개의 퀸이 모두 놓여있는 경우의 입력은 없다.

첫 번째 줄에 정수 $A\_1$, $A\_2$, $A\_3$, $\cdots$, $A\_N$를 출력한다. $A\_i$는 $i$번째 행에 있는 퀸의 열의 번호를 의미한다. $(1 \le A\_i \le N)$

만약 $N$개의 퀸을 놓을 수 없다면 -1을 출력한다.

• $N = 1002001$
• $Q = 1001$
• 이 문제의 채점 데이터에는 $1$개의 데이터만 존재한다.
  • n_queen_special.in