問題文
在AtCoder王国 有 N 个城市。N 在每个城镇 它的编号最大为 1 从 N 并且 1 高桥君进城 青木君住在 N 。
街道之间 M 由主干道连接。每条道路都是单向的,但两个城市之间可能存在多条道路。特别地,一条前进道路和一条反向道路的存在可以允许双向行驶。
有传言称AtCoder王国将分为两个王国:高桥王国和青木王国。似乎将进行划分以满足以下条件。 一些
- N 城镇将成为高桥王国,其余的将成为青木王国。
- 高桥王国有一座城镇。 1 然而,青木王国有一座城镇。 N 始终包含在内。
- 从高桥王国到青木王国的所有道路都将被拆除。也就是说,所有起点属于高桥王国、终点属于青木王国的道路都将被移除。
- 进行划分,以使要移除的道路数量最小化。
满足这些要求的分区方法不一定是唯一的。因此,许多公民担心国家将如何分裂。
所以你的工作是创建一个程序来回答公众的问题。给定两个城市作为问题,编写一个程序来回答每个问题:“它们是否有可能属于同一个国家?”和“它们是否有可能属于不同的国家?”
入力
输入是按以下格式从标准输入给出的。
N M a_1 b_1 a_2 b_2 : a_M b_M Q c_1 d_1 c_2 d_2 : c_Q d_Q
- 1 行中城镇数量 N (1 ≦ N ≦ 5,000)和道路数量 代表第 M (1 ≦ M ≦ 50,000)。
- 2 从线 M 行数过多 i 行中,i 条路径的整数 a_i,b_i (1≦a_i, b_i≦N, a_i ≠ b_i) 用空格分隔。这就是路 i 是城市 a_i 离开城镇 表示已达到 b_i 。
- M+1 行包含一个整数,表示公众提出的问题数。 在 Q (1≦Q≦100,000)。
- M+2 从线 Q 行中, 代表第j 行中,j 个问题的整数 给出 c_j, d_j (1 ≦ c_j, d_j ≦ N, c_j ≠ d_j)。这是j 第一个问题是城市 c_j 和城市 表示与 d_j 相关。 请提供
出力
Q 问题的答案。 1 逐行输出。 问题 j 的答案应由两个单词组成,并用空格分隔。
- 第一个词是城镇。 指示 c_j 和城市 表示与 d_j 是否有可能属于同一个国家。如果有可能属于同一个国家,则输出YES,否则输出NO。
- 第二个词是城镇。 指示 c_j 和城市 表示与 d_j 是否有可能属于其他国家/地区。如果该人有可能属于不同国家,则输出YES,否则输出NO。 如果您对满足
在输出末尾包含换行符。
部分点
针对此问题设置了部分分数。
- N ≦ 100, M ≦ 1,000, Q ≦ 100 的数据集回答正确,您将获得 20 分。
- 如果您在没有附加限制的情况下在数据集上正确回答,您将获得额外的 80 分。
入力例1
3 5 1 2 1 2 1 2 2 3 2 3 3 1 2 2 3 1 3
出力例1
YES NO NO YES NO YES
请注意,两个城市之间可能存在多条道路。
入力例2
3 5 3 2 3 2 3 2 2 1 2 1 3 1 2 2 3 1 3
出力例2
YES YES YES YES NO YES
请注意,仅从高桥王国到青木王国的道路将被移除。
入力例3
8 10 1 2 1 3 1 4 2 3 3 5 4 6 5 8 6 7 6 8 7 8 7 1 2 2 3 2 6 3 6 4 5 5 6 6 7
出力例3
YES NO YES NO NO YES NO YES YES YES YES YES YES NO