N-Queen (특수)

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개뿐이다.