分数: 800 点
问题陈述
给你一个正整数 N 和排列 P of (1,2,\dots,N).
当有一棵树 N 顶点编号 1,2,\dots,N,Snuke和Takahashi按照以下规则移动:
- Snuke 指定了一个排列 Q of (1,2,\dots,N) 使得高桥返回的序列在遵循以下规则时在字典顺序上是最大的。
- 高桥,位于顶点
树的 1 ,首先接收 Q 并初始化一个整数序列 R 的长度-1 序列 (Q_1)。然后,他动了 N-1 次如下,并返回最终的 R:
- 访问顶点 i 最小 Q_i 与先前访问过的顶点相邻但尚未访问过的顶点(可以证明总是存在一个这样的顶点)。然后,追加 Q_i 到结束 R.
这里,顶点 1 被认为最初已被访问。
判断是否存在让Takahashi返回的树 P.
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1 \le T \le 10^5
- 1 \le N \le 2 \times 10^5
- P 是一个排列 (1,2,\dots,N).
- 总和 N 所有测试用例最多 2 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N P_1 P_2 \ldots P_N
输出
输出 T 行。
的 i- 第行应包含 Yes 如果存在满足条件的树 i- 第一个测试用例,以及 No 否则。
示例输入 1
3 4 4 2 3 1 4 4 1 3 2 11 11 8 9 6 7 10 3 4 5 1 2
示例输出 1
Yes No Yes
对于第一个测试用例,具有四个顶点的树,顶点之间有边 1-2, 1-3,和 2-4 满足条件。
如果 Snuke 指定 Q=(4,3,2,1),高桥访问顶点 1,3,2,4 按此顺序并返回 R=(4,2,3,1)。不管怎样 Q Snuke 指定,不可能让 Takahashi 返回字典序大于的序列 (4,2,3,1),所以最终返回的序列是 (4,2,3,1).
对于第二个测试用例,可以证明不存在满足条件的树。