华师一附中OI组

标题: P2189 小Z的传感器 [打印本页]

作者: admin 时间: 2018-5-26 21:02
标题: P2189 小Z的传感器
https://www.luogu.org/problemnew/show/P2189

题目描述
众所周知，小 Z 家是个豪宅，有 n 个房间，并通过 m 条通道相连（家当然是连通的）。

有一天，小 Y 想趁小 Z 不在偷偷光顾他家，并决定到他家的每个房间至少逛一次。不幸的是，小X 家有 k 个房间装了传感器，该传感器会在第一次有人到访的时候返回信息。

当小 Z 回到家时，就发现小 Y 来过了，小 Y 也如实地告诉了小 Z 自己到每个房间至少逛了一次。

然而，小 Z 仔细研究了传感器返回信息的先后顺序，怀疑个别传感器可能返回信息有延迟。

为了验证自己的推断，连同这一次在内，他一共让小 Y 到他家来了 q 次。他想判断每次传感器返回信息的先后顺序是否可能出现，希望你帮帮他。

输入输出格式
输入格式：
第一行包含四个整数 n，m，k，q。

接下来 m 行，每行包含两个整数 x，y，表示房间 x 和房间 y 有一条双向通道相连。

接下来 q 行，每行包含 k 个整数，表示每次按先后顺序返回信息的传感器所在房间的编号。

输出格式：
q 行，每行包含一个字符串“Yes”或“No”，表示每次传感器返回信息的先后顺序是否可能出现。

输入输出样例
输入样例#1：
5 5 3 2
1 2
2 3
3 1
1 4
4 5
4 2 1
4 1 2
输出样例#1：
No
Yes

欢迎光临华师一附中OI组 (http://hsyit.cn/)