← 返回题目列表

Codeforces · 2201/B

B. 回忆数字

中文机器翻译题面 查看原题

有 $$$2n$$$ 卡片,上面写有数字 $$$1,1,2,2,\ldots,n,n$$$。换句话说,对于所有 $$$j=1,2,\ldots,n$$$,有 正是 $$$2$$$ 卡,号码为 $$$j$$$。每张卡片的正面仅写有一个数字。

您将玩翻牌游戏。最初,所有 $$$2n$$$ 卡都放在背面(没有数字的一面)。在每个回合中,你翻转 正好两个 卡。如果两张卡的号码相同, 丢弃 两张牌。否则,您将它们翻转回原来的位置。当所有 $$$2n$$$ 卡都被丢弃时,您就赢了。请注意,你这样做 不 必须同时翻动两张牌,所以你可以在看到第一张牌的数字后决定选择第二张牌。

考虑以下“贪婪”算法来玩游戏。最初,$$$2n$$$ 卡被任意排成一行。那么你每回合的策略如下:

  • 如果有两张牌 你之前翻过 和 有相同的号码,翻转那两张牌。
  • 否则,翻转 第一张牌$$$^\text{*}$$$ 您从未翻转过第一个。假设这张卡的号码为 $$$x$$$。
    • 之后,如果你之前翻过另一张牌并且 的号码为 $$$x$$$,翻开那张牌。
    • 否则,翻转 第一张牌$$$^{\text{*}}$$$ 到目前为止你从未翻转过(包括本回合)作为第二个。

可以证明算法的策略在每一回合都是唯一确定的。

您必须解决关于上述算法的以下问题。

  • 给定 $$$n$$$ 和 $$$k$$$,请找到上述算法所采用的 $$$2n$$$ 卡的方向 正是 $$$k$$$ 赢得了比赛。

此外,如果不存在这样的方向,请报告。

$$$^{\text{*}}$$$这里,某个条件的“第一张牌”是指该行中最早满足该条件的牌。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 300\,000$$$, $$$1 \le k \le 1\,000\,000$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$300\,000$$$。

输出

如果存在满足条件的卡片方向,则输出“是”另起一行。

然后,在下一行输出$$$2n$$$整数$$$a_1,a_2,\ldots,a_{2n-1},a_{2n}$$$。这里,$$$a_i$$$是写在第$$$i$$$卡上的数字。

请注意,序列 $$$a$$$ 必须满足以下条件:

  • 对于每个 $$$1 \le i \le 2n$$$, $$$1 \le a_i \le n$$$;
  • 对于每个 $$$1 \le j \le n$$$,$$$j$$$ 出现在 $$$a$$$ 中 正是 两次;
  • 当牌按此顺序放置时,上述算法恰好需要 $$$k$$$ 轮才能赢得游戏。

如果有多个解决方案,请打印其中任何一个。

如果没有满足条件的卡片方向,则输出“NO" 在单独的一行上。

任何情况下都可以输出答案。例如,字符串“是", "是的“,和”是”也将被视为积极响应。

示例

输入
复制

6
2 3
3 4
3 2
3 5
6 10
6 67

输出
复制

YES
2 1 2 1
YES
1 3 2 2 1 3
NO
YES
1 2 3 1 2 3
YES
2 1 3 4 5 4 1 2 6 5 6 3
NO

注意

对于第一个测试用例,每轮的选择如下:

  1. $$$[\color{red}{2},\color{red}{1},2,1]$$$:两张牌的数字不同,因此它们被翻转回原来的位置。
  2. $$$[\color{red}{2},\color{blue}{1},\color{red}{2},1]$$$:两张牌的数字相同,因此它们被丢弃。
  3. $$$[\color{red}{1},\color{red}{1}]$$$:两张牌的数字相同,因此它们被丢弃。

这里,红色数字表示当前回合翻过的牌,蓝色数字表示之前翻过的牌。

对于第四个测试用例,每轮的选择如下:

  1. $$$[\color{red}{1},\color{red}{2},3,1,2,3]$$$:两张牌的数字不同,因此它们被翻转回原来的位置。
  2. $$$[\color{blue}{1},\color{blue}{2},\color{red}{3},\color{red}{1},2,3]$$$:两张牌的数字不同,因此它们被翻转回原来的位置。
  3. $$$[\color{red}{1},\color{blue}{2},\color{blue}{3},\color{red}{1},2,3]$$$:两张牌的数字相同,因此它们被丢弃。
  4. $$$[\color{red}{2},\color{blue}{3},\color{red}{2},3]$$$:两张牌的数字相同,因此它们被丢弃。
  5. $$$[\color{red}{3},\color{red}{3}]$$$:两张牌的数字相同,因此它们被丢弃。

该算法恰好花了 $$$k=5$$$ 轮来赢得比赛。