삼각분할과 삼각형 개수 수열

다각형의 삼각분할은 꼭짓점끼리 이은 선분을 모아 다각형을 삼각형으로 나눈 것이다. 선분은 반드시 다각형 내부에 있어야 하고, 꼭짓점이 아닌 곳에서 다른 선분과 만나면 안 된다. 꼭짓점이 $n$개인 다각형을 삼각분할하면 삼각형이 항상 $n-2$개 생긴다.

한 꼭짓점에서 출발해 변을 따라 한 바퀴 돌면서 각 꼭짓점에 닿아 있는 삼각형의 개수를 차례로 적은 것을 삼각형 개수 수열이라고 한다. 아래 세 수열은 모두 삼각형 개수 수열이다. A와 B는 꼭짓점이 6개인 다각형에서, C는 꼭짓점이 12개인 다각형에서 나왔다.

• A: 1 3 1 3 1 3
• B: 2 2 1 4 1 2
• C: 1 2 3 2 1 6 1 2 3 2 1 6

양의 정수 $N$개로 이루어진 수열이 주어졌을 때, 이 수열을 삼각형 개수 수열로 가지는 삼각분할이 있는지 판정하는 프로그램을 작성하시오. 있으면 삼각형을 모두 출력한다.

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

다음 $P$개 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄의 첫 번째 정수는 테스트 케이스 번호 $K$이고, 두 번째 정수는 수열의 길이 $N$이다. ($4 \le N \le 20$) 이어지는 $N$개의 정수가 삼각형 개수 수열이며, 모두 양의 정수다.

각 테스트 케이스마다 테스트 케이스 번호 $K$를 출력하고, 빈칸을 사이에 두고 판정 결과를 출력한다. 주어진 수열을 삼각형 개수 수열로 가지는 삼각분할이 없으면 대문자 N을, 있으면 대문자 Y를 출력한다.

Y를 출력한 경우에는 이어지는 $N-2$개 줄에 삼각형을 한 줄에 하나씩 출력한다. 꼭짓점 번호는 수열에 주어진 순서대로 1번부터 $N$번까지이고, 한 삼각형의 꼭짓점 번호 세 개는 증가하는 순서로 출력한다. 삼각형은 사전순으로 정렬해서 출력한다. $k < l < m$이 한 삼각형이고 $r < s < t$가 다른 삼각형일 때, 아래 조건을 만족하면 첫 번째 삼각형이 두 번째보다 앞선다.

k<r OR (k==r AND l<s) OR (k==r AND l==s AND m<t)

한 수열에 맞는 삼각분할은 있어도 하나뿐이므로 출력은 하나로 정해진다.