# 拨号关系的补全

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

一台拨号装置用不同号码表示元素，多个号码可能代表同一个元素。装置已经记录了若干有向关系，现在希望补全这些关系，形成一个格，同时避免擅自颠倒已有关系。

## 形式化问题描述

偏序 $\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=\{(i,a_i)\mid1\le i\le N\}$$

判断能否只添加关系，得到 $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

### 输入

```text
4
2
2
1
3
2
1
3
3
2
3
1
3
1
2
3
```

### 输出

```text
Y
Y
N
Y
```

### 样例 2

### 输入

```text
3
1
1
5
2
3
4
5
5
4
2
3
4
2
```

### 输出

```text
Y
Y
N
```

## 样例解释

第一组样例中，符号一和二的双向关系已经存在，可把二者映射为同一元素。三个符号组成的单向环无法合法补全，因此第一组输入的第三个测试输出 `N` .每个符号仅与自身有关时，可以增加关系将这些元素排成全序，得到一个格。

![允许的二元环与不能补全的三元环](assets/completion.svg)

图中箭头表示初始关系；左右图分别对应 `Y` 和 `N` .第二组输入还覆盖单符号、链形关系和附带链的三元环。

## 数据范围与保证

每组满足 $1\le N\le2\times10^5$ ，$1\le a_i\le N$ .同一输入文件中所有 $N$ 的和不超过 $4\times10^5$ .允许自环，也允许不同符号表示同一元素。

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |