2059. 里氏代换(25分)

里氏代换原则是由 2008 年图灵奖得主 Barbara Liskov 和 Jeannette Wing 提出的面向对象设计原则,可通俗表述为:在软件中如果能使用基类对象,那么一定能够使用其子类对象。把基类都替换成它的子类,程序将不会产生任何错误和异常,反过来则不成立,如果一个软件实体使用的是一个子类的话,那么它不一定能够使用基类。

以 Java 标准库的集合类为例,下面的 UML 类图的箭头代表父子类(泛化)/接口(实现)关系,你可以通俗理解为子类指向父类。例如,Queue 是 Collection 的子类,Set 是 TreeSet 的父类。因此,所有能用 Collection 的地方一定能用 Queue,但能用 TreeSet 的地方不一定能用 Set。

为兼容各编程语言的差异性,你应当认为一个类可以有任意多个直接父类和任意多个直接子类。

对一个已知的类图,给定类图里的两个类 u,v,你需要判断 u 是否是 v 的子类。

输入

输入一行两个整数 n,m(2\le n\le 10^4,0\le m\le 2\times 10^5),代表类图里类的个数,以及实现关系数目。

接下来输入 m 行,每行两个整数 u,v(1\le u,v\le n,u\neq v),代表 uv 的子类。

保证不存在环,即不存在这样的边 a\to b,b\to c,\cdots,x\to a

不保证只有一个类没有父类,不保证类图弱连通。

输出

接下来输入一行一个整数 q(1\le q\le 10^5),代表一次询问。

接下来输入 q 行,每行两个整数 u,v(1\le u,v\le n,u\neq v),代表询问 u 是否是 v 的子类。

对每个询问,若 uv 的子类,输出一行 Yes,否则输出一行 No

样例

标准输入 复制文本
5 5
2 1
3 1
4 2
4 3
5 2
4
1 4
4 1
5 2
5 3
标准输出 复制文本
No
Yes
Yes
No

提示

对样例,如图所示:

来源

2023 天梯赛选拔赛 (重现)

登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 6
通过 1