Permutations and Cycles (Minimum Version)

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

요약
각 n과 x에 대해 인접한 두 값의 합이 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 minimum 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 minimum 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

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