题目描述

一个大型通讯网络，共有 $N$ 个节点，它们通过 $M$ 条双向线路相连。不同的网络节点承载着不同的负荷。

通讯部门要求网络管理员按照网络节点承载负荷从大到小的顺序，依次关闭每个节点，测试每个阶段网络的连通性。每当关闭一个节点时，所有与该节点直接连接的线路也会关闭。

通讯部门要求管理员记录，每个关闭节点之前，当前的网络是否是连通的。即：从任意一个未被关闭的节点到达其他任何一个未被关闭的节点，可以正常通讯。

输入格式

第 $1$ 行输入 $2$ 个整数 $N, M$。

接下来的 $M$ 行，每行两个整数 $U, V$，描述连接节点 $U$ 和 $V$ 的线路。

最后 $N$ 行，每行一个整数，表示按照负荷从大到小的顺序，依次关闭的节点编号。

输出格式

输出 $N$ 行，每行包含 Y 或 N，Y 表示网络连通，N 表示网络不连通。

样例

输入

5 4
1 2
1 5
5 3
5 4
4
5
2
3
1

输出

Y
Y
N
N
Y

数据范围

对于 $40\%$ 的数据，$1 \le N, M \le 3000$。

对于 $100\%$ 的数据，$1 \le N, M \le 2 \times 10^5$，$1 \le U, V \le N$。