Permutations and Cycles (Minimum Version)
Time limit2sMemory limit2048 MB
Given n and x, build a permutation of 1 to n where each adjacent pair sums to at most x, using the fewest cycles.
- Level
Medium5 of 10
- Topics
- Array, Greedy, Implementation
- Solved
- No attempts yet
Problem
For a given , a permutation of size is called good if for each the condition holds. Find any good permutation with the minimum number of cycles.
A permutation of size is a sequence of distinct integers from to .
A cycle of a permutation is a sequence of indices such that , , , . Cycles that differ only by a cyclic shift of the sequence are considered the same.
Input
The first line contains an integer (), the number of test cases. The test cases follow.
Each test case is given on one line with two integers () and (). These constraints guarantee that at least one good permutation exists.
The sum of over all test cases does not exceed .
Output
For each test case, print two lines. The first line contains the minimum number of cycles in a good permutation of length . The second line contains the integers of the permutation. If multiple such permutations exist, print any one of them.