30246번 - 🧩 N-Queen (Quantum) 스페셜 저지

문제

N-Queen 문제는 $N\times N$ 보드에 서로 공격할 수 없는 퀸 $N$개를 배치하는 문제이다. 이 문제에서는 특별히 양자 세계에서의 N-Queen를 새롭게 정의한다. 양자 세계에서의 N-Queen 문제는 다음과 같이 정의된다.

• $N\times N$ 보드의 각 칸에 퀸을 $[0,1]$ 구간의 임의의 실수만큼 배치할 수 있다.
• 각 행에 있는 퀸의 수의 합은 반드시 1ドル$이다.
• 각 열에 있는 퀸의 수의 합은 반드시 1ドル$이다.
• 각 대각선에 있는 퀸의 수의 합은 1ドル$ 이하이다.
• 보드에서 위 조건들을 만족하는 퀸의 배치를 찾아야 한다.

그러나 퀸이 없는 보드에서 이 문제를 해결하는 것은 너무 쉽다. 일부 칸에 배치 퀸의 개수가 이미 고정되어 있을 때, 퀸을 놓는 방법 한 가지를 출력해 보자.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\le T\le 20)$

각 테스트 케이스의 첫 번째 줄에는 보드의 크기 $N$이 주어진다. $(1\le N\le 40)$

다음 줄부터 총 $N$개의 줄에 걸쳐 각 줄에 $N$개씩 총 $N^2$개의 실수가 주어진다. 그 중 $i$번째 행의 $j$번째 열에는 해당하는 칸에 배치된 퀸의 개수를 의미하는 $B_{i,j}$가 주어진다.

각 실수 $B_{i,j}$는 $-1$이거나 $[0,1]$ 구간의 실수이다.

• $-1$인 경우 이는 해당하는 칸에 배치된 퀸의 개수가 고정되어 있지 않음을 의미한다.
• $[0,1]$ 구간의 실수인 경우 해당하는 칸에 배치된 퀸의 개수가 $B_{i,j}$로 고정되어 있음을 의미한다. 이때 $B_{i,j}$는 소수점 아래 7ドル$자리까지 주어진다.

모든 테스트케이스에서 $N$의 합은 40ドル$ 이하이다.

출력

각 테스트 케이스에 대해, 조건을 만족하는 퀸의 배치가 존재한다면, YES를 한 줄에 출력하고 다음 줄부터 입력과 같은 형식으로 조건을 만족하는 퀸의 배치를 출력한다.

출력된 퀸의 배치는 다음 조건들을 만족해야 한다.

• 각 행에 있는 퀸의 수의 합은 1ドル-10^{-6}$ 이상 1ドル+10^{-6}$ 이하이다.
• 각 열에 있는 퀸의 수의 합은 1ドル-10^{-6}$ 이상 1ドル+10^{-6}$ 이하이다.
• 각 대각선에 있는 퀸의 수의 합은 1ドル+10^{-6}$ 이하이다.
• 퀸의 개수가 고정된 칸에서 출력된 퀸의 수는 $B_{i,j}$와의 절대 오차가 10ドル^{-9}$ 이하이다.

단, 이미 고정된 퀸의 개수에 대해서 (오차 범위를 제외하고) 지문의 조건을 만족하는 퀸의 배치가 실제로 존재할 수 없다면, 오차 범위 내의 배치가 출력되더라도 를 받는다.

조건을 만족하는 퀸의 배치가 존재하지 않는다면, NO를 한 줄에 출력한다.

제한

힌트