← 返回题目列表

AtCoder · codefestival_2015_ex_a

A. 高桥王国和青木王国

中文机器翻译题面 查看原题

問題文

在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