Permutations and Cycles (Maximum Version)

시간 제한2초메모리 제한2048 MB

요약
인접한 두 값의 합이 x 이하가 되는 순열 가운데 사이클 수가 최대인 순열을 각 테스트마다 하나씩 구한다.
난이도

어려움10점 중 8점

유형
조합론, 그리디, 구현
정답자
아직 제출이 없습니다

문제

For a given xx, a permutation of size nn is called good if for each 1≤i<n1 \le i < n the condition p_i+p_i+1≤xp\_i + p\_{i + 1} \le x holds. Find any good permutation with the maximum number of cycles.

A permutation of size nn is a sequence of nn distinct integers from 11 to nn.

A cycle of a permutation pp is a sequence of indices i_1,i_2,…,i_ki\_1, i\_2, \ldots, i\_k such that p_i_1=i_2p\_{i\_1} = i\_2, p_i_2=i_3p\_{i\_2} = i\_3, …\ldots, p_i_k=i_1p\_{i\_k} = i\_1. The cycles obtained by a cyclic shifting of the sequence are considered to be the same.

입력

The first line contains an integer tt (1≤t≤2⋅1051 \le t \le 2 \cdot 10^5), the number of test cases. The test cases follow.

Each test case is given on a line with two integers nn (2≤n≤2⋅1052 \le n \le 2 \cdot 10^5) and xx (n+1≤x≤2⋅n−1n + 1 \le x \le 2 \cdot n - 1). These constraints guarantee that at least one good permutation exists.

The sum of nn over all test cases does not exceed 2⋅1052 \cdot 10^5.

출력

For each test case, print two lines. The first one should contain the maximum number of cycles in a good permutation of length nn. The second line should consist of nn integers: the permutation itself. If multiple such permutations exist, print any one of them.

예제1

  1. 예제 1

    입력
    3
    2 3
    3 4
    3 5
    
    예상 출력
    2
    1 2
    2
    2 1 3
    3
    1 2 3