영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
You are given a list of N positive integers a_1, a_2, …, a_N. Your goal is to sort the list. In one move, you may swap two numbers in the list if one of them is a divisor of the other. In other words, you may swap a_i and a_j if a_i ≡ 0 (mod a_j) or a_j ≡ 0 (mod a_i). In many programming languages, you can check a_i ≡ 0 (mod a_j) by testing whether a_i % a_j equals 0 (i.e., the remainder of integer division is zero).
Determine if it is possible to sort the list, and if so, output a sequence of moves that sorts the list.
Input
The first line contains two integers N and X (1 ≤ N ≤ 1000, 0 ≤ X ≤ 1), where N is the number of elements in the list and X is a flag indicating whether you need to output the sequence of moves.
The second line contains N integers a_1, a_2, …, a_N (1 ≤ a_i ≤ 10^6).
Output
If it is impossible to sort the list, output NEJ.
If it is possible to sort the list, first output JA on the first line. Then output an integer M on a line, the number of moves you will make. This number must be at most 10^6. Then output M lines, each containing two integers i, j (1 ≤ i,j ≤ N), indicating that you swap a_i and a_j.
If X = 0, it suffices to output JA or NEJ correctly. You do not need to output the moves, and you will not be judged wrong if you do (even if the moves are incorrect).
Scoring
Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 17 | N ≤ 10 |
| 2 | 10 | There are at most 2 unique values in the list. |
| 3 | 13 | There are at most 3 unique values in the list. |
| 4 | 30 | X = 0 |
| 5 | 12 | a_1 = 1 |
| 6 | 18 | No additional constraints. |
예제
예제 1
5 1 9 8 40 3 5
JA 3 2 3 2 5 1 4
예제 2
2 1 9 5
NEJ
예제 3
4 0 1 7 5 3
JA