You are given non-negative integers .
Define a sequence of length as follows.
You may perform the following operation any number of times: choose two distinct indices and replace both and with .
Find the minimum number of operations required to make all elements of equal, and output one sequence of operations attaining the minimum. If it is impossible, print .
If it is possible, it can be proven that under the given constraints, the minimum number of operations is always at most .
Partial scoring is available for this problem. See the Scoring section for details.
The input is given from Standard Input in the following format:
If it is impossible, print on one line.
Otherwise, first print the minimum number of operations . Then print lines; on the -th line, print the two indices chosen in the -th operation, in the following format:
The score for each test case, as a percentage of the score of the subtask containing it, is calculated as follows.
If it is impossible to make all elements equal:
If it is possible to make all elements equal:
Every operation must satisfy and , and the printed operations must actually make all elements equal. If there are multiple valid answers, print any of them.
The additional conditions used in the subtasks are defined as follows.
Additional Condition A
Additional Condition B
| 3 | 4 | Additional Condition A is satisfied, and . |
| 4 | 6 | Additional Condition A is satisfied, and . |
| 5 | 11 | Additional Condition A is satisfied. |
| 6 | 6 | Additional Condition B is satisfied, and . |
| 7 | 9 | Additional Condition B is satisfied, and . |
| 8 | 16 | Additional Condition B is satisfied. |
| 9 | 9 | . |
| 10 | 13 | . |
| 11 | 18 | No additional constraints. |
The score for each subtask is the minimum of the scores for the test cases in that subtask.