SP7188 ESJAIL - Escape from Jail

Harry 是国际通用犯罪者监狱（ICPC）的囚犯，这里是全球最严密的监狱。独特的是，这个监狱由一位老玩家设计。它并不是完全封闭，而是需要者具备极其快速且合理的思维才能逃脱。监狱由 $N$ 个房间构成，这些房间通过 $M$ 条双向走廊连接。每个房间要么是空的，要么有一扇无法破坏的门，或者有一把钥匙。没有任何房间既有门又有钥匙。监狱里总共有 $K$ 扇门和 $K$ 把钥匙，每把钥匙和每扇门都是一一对应的。如果某个房间有门，那么无论从哪个方向进入，都需要对应的钥匙。 Harry 找到了完整的监狱地图，包括所有门和钥匙的位置，他想弄清楚如何逃出这个地方。根据地图，Harry 当前在房间 1，而出口在房间 $N$。请根据地图信息判断，Harry 是否能逃脱，还是永远困在这里。

输入包含多个测试用例，每个测试用例由多行组成。每个测试用例的第一行包含三个整数 $N$、$K$ 和 $M$，用空格隔开。其中 $N$ 是监狱的房间总数，范围是 $4 \leq N \leq 10^3$；$K$ 是门和钥匙的数量，范围是 $1 \leq K \leq 10^3$；$M$ 是走廊的数量，范围是 $1 \leq M \leq 10^4$。接下来的 $K$ 行分别指出钥匙和对应门所在的房间，以两个整数 $A$ 和 $B$ 表示：房间 $A$ 有可以打开房间 $B$ 的钥匙（$2 \leq A, B \leq N-1$，$A \neq B$）。接下来的 $M$ 行描述走廊信息，每行包含两个整数 $C$ 和 $D$，表示房间 $C$ 和 $D$ 之间有一条走廊（$1 \leq C, D \leq N$，$C \neq D$）。输入的最后一行是三个 −1，用空格隔开，不应作为测试用例处理。

对于每个测试用例，输出一行。如果 Harry 能够成功逃脱监狱，则输出大写字母 “Y”；否则，输出大写字母 “N”。 **本翻译由 AI 自动生成**