#P17709. [2026年江苏省队集训]以物易物
[2026年江苏省队集训]以物易物
题面描述
你有 棵闪灵草。现在第 棵闪灵草拥有珠子 。你希望通过一些珠子的交换最后让第 棵闪灵草拥有珠子 。
但是交换也是有规则的,让第 棵闪灵草和第 棵闪灵草交换珠子有以下的要求:
- 闪灵草很矮,因此只有相邻的闪灵草可以交换,即 。
- 第 棵对珠子有一个喜爱的顺序,这个顺序可以被一个 的排列 描述,越靠前的珠子越喜欢。
闪灵草是很暴躁的生物,因此每次交换需要满足参与交换的两棵闪灵草都更喜欢交换后的物品。
具体地,设 和 当前的物品分别为 ,需要满足:
- 在 中, 出现的位置比 靠前
- 在 中, 出现的位置比 靠前
如果某一次交换没有满足上面两点的话,它们就会在下大雪的夜晚拿斧子劈开你的家门。
现在你需要构造一种满足条件的交换方案,或者报告无解。
输入格式
第一行一个正整数 ,表示数据组数。
每组数据第一行一个正整数 ,表示闪灵草的数量。
接下来 行,第 行一个 的排列 ,表示第 棵闪灵草的喜爱顺序。
接下来一行两个正整数 ,表示你最后需要让第 棵闪灵草拥有珠子 。
输出格式
对于每组数据,如果不存在合法的构造方式,则输出 No。
否则第一行输出 Yes。
接下来一行输出一个正整数 ,表示你的构造需要的步数,你需要保证 。
接下来 行每行两个正整数 ,表示你要交换第 棵闪灵草和第 棵闪灵草的珠子。
输入输出样例
输入样例 #1
3
2
1 2
1 2
1 2
4
3 4 2 1
4 3 1 2
2 1 4 3
1 3 2 4
4 2
2
2 1
1 2
2 1
输出样例 #1
No
Yes
3
2 1
3 4
3 2
Yes
1
2 1
数据范围
对于所有数据,,保证每个 是 的一个排列。
| 子任务编号 | 其它性质 | 分值 | |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | 保证数据随机 | ||
| 5 | |||
| 6 |
数据随机方式为:每组数据首先选定一个 ,然后 在 内等概率随机,每个 在所有 的排列中随机。
在此基础上,如果你正确判断了一个子任务所有数据点是否有解,你可以获得这个子任务 的分数,但请注意你仍然需要输出格式的方案构造,如输出:
Yes
0