시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 21 10 9 56.250%

문제

다각형의 삼각분할이란 다각형을 삼각형으로 나누는 꼭지점을 연결하는 직선의 집합이다. 직선은 반드시 다각형 내부에 있어야 하며, 꼭지점을 제외한 다른 곳에서 다른 직선과 교차하면 안된다. 

위의 그림에서 굵은 선은 다각형의 변을 나타내고, 가는 선은 삼각분할을 나타낸다. 꼭지점이 n개인 다각형을 삼각분할하면 (n-2)개의 삼각형을 만들 수 있다.

한 꼭지점에서 시작해 변을 따라 이동하면서 각 꼭지점에 있는 삼각형의 개수를 나열한 것을 삼각형 개수 수열이라고 한다. 위의 그림에 나와있는 다각형의 삼각형 개수 수열은 아래와 같다. 가장 왼쪽 위에 있는 꼭지점에서 시작한다.

  • 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 ≤ P ≤ 1000)가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 숫자는 테스트 케이스 번호 K이며, 두 번째 숫자는 수열의 길이 N (4 ≤ N ≤ 20)이다. 다음 N개의 숫자는 삼각형 개수 수열이다.

출력

입력으로 주어진 수열이 삼각형 개수 수열이 아닌 경우에는 테스트 케이스 번호 K와 알파벳 대문자 "N"을 출력한다.

올바른 경우에는 테스트 케이스 번호 K와 알파벳 대문자 "Y"를 출력한다. 다음 (N-2)개 줄에는 어떤 꼭지점이 삼각형을 이루는지 한 줄에 하나씩 출력한다. 꼭지점은 입력으로 주어진 순서대로 1번부터 시작하며, 사전순으로 정렬해서 출력한다. k < l < m이 한 삼각형이고, r < s < t가 다른 삼각형일 때, 아래 조건을 만족하면 첫 번째 삼각형이 두 번째보다 사전순으로 앞선다.

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

예제 입력

4
1 6 1 3 1 3 1 3
2 6 1 3 2 2 1 3
3 12 1 2 3 2 1 6 1 2 3 2 1 6
4 20 1 2 3 2 1 6 1 2 3 2 1 6 1 3 2 2 1 3 1 2

예제 출력

1 Y
1 2 6
2 3 4
2 4 6
4 5 6
2 N
3 Y
1 2 12
2 3 12
3 4 6
3 6 12
4 5 6
6 7 8
6 8 9
6 9 12
9 10 12
10 11 12
4 N

힌트