拨号关系的补全¶
预估时间限制：0.5 秒。内存限制：128 MB。
实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
一台拨号装置用不同号码表示元素，多个号码可能代表同一个元素。装置已经记录了若干有向关系，现在希望补全这些关系，形成一个格，同时避免擅自颠倒已有关系。
形式化问题描述¶
偏序 \(\le\) 是满足反身性、反对称性和传递性的关系：\(x\le x\) ；若 \(x\le y\) 且 \(y\le x\) ，则 \(x=y\) ；若 \(x\le y\) 且 \(y\le z\) ，则 \(x\le z\) .
元素 \(u\) 是 \(x,y\) 的上界，指 \(x\le u\) 且 \(y\le u\) .若某个上界不大于任何其他上界，它称为上确界。下界和下确界按相反方向定义。非空偏序集中的任意两个元素都有上确界与下确界时，称这个偏序集为格。
符号与元素不同：允许多个符号表示同一个元素。设 \(f\) 把每个符号映射到一个元素，并且每个元素至少有一个符号表示。符号关系表示偏序，指对所有符号 \(i,j\) ，关系存在当且仅当 \(f(i)\le f(j)\) .元素集合及映射 \(f\) 都可以选择，不作为输入给出。
本题有 \(N\) 个符号，编号为 \(1,\ldots,N\) .输入为每个符号指定一个符号 \(a_i\) ，初始关系集为
判断能否只添加关系，得到 \(R'\supseteq R\) ，使其表示某个格，并满足：对于每条初始关系 \((i,j)\in R\) ，不能新加入其反向关系 \((j,i)\) .若反向关系本来已在 \(R\) 中，则保留它不受限制。形式化地，要求 \((j,i)\notin R'\setminus R\) .
这里只需判断是否存在这样的补全，不需要输出元素映射或补全后的关系。
输入格式¶
第一行一个整数 \(T\) ，表示数据组数。每组数据第一行一个整数 \(N\) ；接下来 \(N\) 行，第 \(i\) 行一个整数 \(a_i\) ，表示初始关系 \((i,a_i)\) .
输出格式¶
每组输出一行一个字符：能够按要求补全时输出 Y ，否则输出 N .
样例¶
样例 1¶
输入¶
4
2
2
1
3
2
1
3
3
2
3
1
3
1
2
3
输出¶
Y
Y
N
Y
样例 2¶
输入¶
3
1
1
5
2
3
4
5
5
4
2
3
4
2
输出¶
Y
Y
N
样例解释¶
第一组样例中，符号一和二的双向关系已经存在，可把二者映射为同一元素。三个符号组成的单向环无法合法补全，因此第一组输入的第三个测试输出 N .每个符号仅与自身有关时，可以增加关系将这些元素排成全序，得到一个格。
图中箭头表示初始关系；左右图分别对应 Y 和 N .第二组输入还覆盖单符号、链形关系和附带链的三元环。
数据范围与保证¶
每组满足 \(1\le N\le2\times10^5\) ，\(1\le a_i\le N\) .同一输入文件中所有 \(N\) 的和不超过 \(4\times10^5\) .允许自环，也允许不同符号表示同一元素。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |