#CSES2215. 单调子序列

    ID: 395 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>构造排列LISDilworth定理CSES线性dp分支结构

单调子序列

题目背景

翻译自 CSES-2215 题。

题目描述

任务是创建一个包含数字 1,2,,n1, 2, \ldots, n 的排列,使得该排列的最长单调子序列恰好有 kk 个元素。

单调子序列 是指一个递增或递减的子序列。例如,在排列 [2,1,4,5,3][2, 1, 4, 5, 3] 中,一些单调子序列有 [2,4,5][2, 4, 5][4,3][4, 3]

输入格式

第一行包含一个整数 tt,表示测试用例的数量。

接下来的 tt 行,每行包含两个整数 nnkk

输出格式

对于每个测试用例,输出一行表示符合条件的排列。如果没有解,输出 IMPOSSIBLE

样例

3
5 3
5 2
7 7
2 1 4 5 3
IMPOSSIBLE
1 2 3 4 5 6 7

数据范围

  • 1t10001 \le t \le 1000
  • 1kn1001 \le k \le n \le 100