30244번 - 🧩 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

힌트