#P2189. 小Z的传感器
小Z的传感器
题目描述
众所周知,小 Z 家是个豪宅,有 个房间,并通过 条通道相连(家当然是连通的)。
有一天,小 Y 想趁小 Z 不在偷偷光顾他家,并决定到他家的每个房间至少逛一次。不幸的是,小 X 家有 个房间装了传感器,该传感器会在第一次有人到访的时候返回信息。
当小 Z 回到家时,就发现小 Y 来过了,小 Y 也如实地告诉了小 Z 自己到每个房间至少逛了一次。
然而,小 Z 仔细研究了传感器返回信息的先后顺序,怀疑个别传感器可能返回信息有延迟。
为了验证自己的推断,连同这一次在内,他一共让小 Y 到他家来了 次。他想判断每次传感器返回信息的先后顺序是否可能出现,希望你帮帮他。
输入格式
第一行包含四个整数 ,,,。
接下来 行,每行包含两个整数 ,,表示房间 和房间 有一条双向通道相连。
接下来 q 行,每行包含 k 个整数,表示每次按先后顺序返回信息的传感器所在房间的编号。
输出格式
行,每行包含一个字符串“Yes”或“No”,表示每次传感器返回信息的先后顺序是否可能出现。
5 5 3 2
1 2
2 3
3 1
1 4
4 5
4 2 1
4 1 2
No
Yes
提示
【数据规模】
对于 的数据,;
对于 的数据,;
对于 的数据,;
对于 的数据,$1 \le k \le n \le 10^5,1 \le m \le 2 \times 10^5,1 \le q \le 5,x \neq y$。