이 문제는 인터랙티브 문제입니다.

바다, 다시 만났구나. 다음 여름 방학에도 행복하길 바라! 아주 오래전, 우나와 카모메는 이미 좋은 친구였다.

그들은 게임을 하는 것을 좋아했다. 지난번, 우나가 발명한 게임은 카모메의 뛰어난 전략으로 쉽게 풀렸다. 이번에는 우나가 새로운 게임을 가져왔다.

우나는 $n$개의 노드를 가진 트리를 생각하고 있다. 카모메는 최대 $n$번의 쿼리를 할 수 있다: * 카모메는 순열 $P_1, P_2, \dots, P_n$ (단, $0 \le P_i \le n-1$이고 모든 $P_i$는 서로 다름)을 우나에게 알려줄 수 있다. 그러면 우나는 노드 $i$에 가중치 $2^{P_i}$가 할당되었을 때 트리의 가중치 지름의 길이를 카모메에게 알려준다.

하지만 때때로 카모메는 우나가 말썽을 부린다는 것을 알게 된다. 더 구체적으로 말하면, 아무리 많이 물어봐도 트리를 확실하게 결정할 수 없는 경우가 있다. 이런 경우 카모메는 해답이 없다고 보고할 수 있다.

인터랙션 프로토콜

이 문제는 인터랙티브 문제입니다. 각 출력 후에는 반드시 출력 버퍼를 비워야 합니다. 출력 버퍼를 비우려면 다음을 사용할 수 있습니다: C/C++: fflush(stdout) 또는 cout.flush() Java 및 Kotlin: System.out.flush() * Python: sys.stdout.flush()

먼저, 테스트 케이스의 수 $T$ ($1 < T < 10^4$)를 읽어야 합니다. 각 테스트 케이스마다, 트리의 크기 $n$ ($2 \le n \le 100$, $\sum n^2 < 10^6$)을 읽어야 합니다.

쿼리를 하려면, "? $P_1 P_2 \dots P_n$" 형식으로 한 줄을 출력해야 합니다 (단, $0 \le P_i \le n-1$이고 $1 < i < j \le n$일 때 $P_i \ne P_j$). 그런 다음, 이진 표현으로 된 트리의 지름 가중치를 나타내는 $n$개의 문자로 이루어진 문자열을 읽습니다. 쿼리가 유효하지 않거나, 한 테스트 케이스에서 $n$번보다 많은 쿼리를 하면, 저지 프로그램은 -1을 출력합니다. -1을 읽으면, 정의되지 않은 동작을 피하기 위해 즉시 종료해야 합니다.

트리를 고유하게 결정하는 것이 불가능하다고 판단되면, "! NO"를 출력해야 합니다. 그렇지 않으면, 트리에 간선 $(u_i, v_i)$가 포함됨을 나타내는 "! YES $u_1 v_1 u_2 v_2 \dots u_{n-1} v_{n-1}$" 형식으로 한 줄을 출력해야 합니다. 간선들은 어떤 순서로든 출력할 수 있습니다.

그런 다음, 답이 맞는지 여부를 나타내는 "OK" 또는 "WA"라는 단어를 읽습니다. "WA"를 읽으면, 정의되지 않은 동작을 피하기 위해 즉시 종료해야 합니다. 트리가 결정 불가능하여 YES를 출력했는데, 답이 맞더라도, 우나는 당신이 속임수를 쓰고 있다고 생각하므로 답은 오답으로 간주됩니다.

저지 프로그램은 적응형이 아니므로, 쿼리 후에도 답은 변경되지 않습니다.

예제

입력 1

2
4
1110
1110
OK
3
111
OK

출력 1

? 0 1 2 3
? 2 1 0 3
! YES 1 4 2 4 3 4
? 0 1 2
! NO

참고

테스트 도구가 제공되어 참가자들이 솔루션을 개발하고 테스트할 수 있습니다. 이 도구는 첨부 파일에서 다운로드할 수 있습니다. "-h" 옵션으로 도구를 실행하면 사용법을 설명합니다. 테스트 도구는 실제 저지 프로그램의 일부 기능만 구현하며 일부 테스트 시나리오만 구현합니다.