里氏代换原则是由 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),代表 u 是 v 的子类。
保证不存在环,即不存在这样的边 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 的子类。
对每个询问,若 u 是 v 的子类,输出一行 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 天梯赛选拔赛 (重现)