← 返回题目列表

AtCoder · arc036_d

D. 偶数米

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

問題文

在高桥君居住的国家 有 N 个城市。每个 用整数编号 1 到 N 。 然而,这些城市之间仍然没有交通。 所以政府提供补贴,有所作为。 2 我们决定修建几条连接这两个城市的道路。 每条路都有单独的长度。 待铺设的道路已被绑住 2 您可以从任一国家/地区转移到另一个国家/地区。换句话说,这是一条可以双向行驶的路。

顺便说一句,高桥君喜欢偶数。 高桥君尝试通过公路旅行,以便无论需要多长时间或走了多少次同一条路,总行驶距离都是偶数米。 而且,高桥君不喜欢半途而废,所以他不会中途回头。

高桥有时...2 我们会询问您是否可以在两个城市之间行驶偶数米。 如前所述,我们目前正在增加道路数量,因此请注意,根据您提出问题的时间,偶数米的行驶能力可能会根据新建道路的时间而变化。

城市内出行不包含在总出行距离中。

有关道路建设的信息和高桥君的问题将按时间顺序给出,因此请创建一个程序来回答高桥君的问题。


入力

输入是从标准输入按以下格式给出的

N Q
w_1 x_1 y_1 z_1
w_2 x_2 y_2 z_2
:
w_Q x_Q y_Q z_Q
  • 1 第一行显示高桥君居住的国家的城市数量。 N (1 ≦ N ≦ 10^5) 以及给出的信息条数 Q (1 ≦ Q ≦ 10^5) 用空格分隔。 代表第
  • 2 从线 Q 行数过多 i 行是 一个整数,表示第 i 条信息的整数 w_i, x_i, y_i, z_i 作为空格分隔符给出。每个变量满足以下约束。
    • 1 ≦ w_i ≦ 2
    • 1 ≦ x_i, y_i ≦ N
    • x_i ≠ y_i
    • 1 ≦ z_i ≦ 10^5
  • w_i = 1 当城 x_i 和城市 y_i 之间的长度 z_i 表示铺设一米的道路。
  • w_i = 2 高桥君在城里的时候 x_i 和城市 y_i 移动偶数米。此时 z_i 始终 1 。 当
  • 相同 2 一个城镇可能有多条道路。
  • 高桥君提问时,假设之前输入的所有道路都已完成。 如果正确答案是满足

部分点

针对此问题设置了部分分数。 如果

  • 1 ≦ N ≦ 3,000 , 1 ≦ Q ≦ 3,000 的数据集 如果正确答案是满足 30 点。
  • 1 ≦ N ≦ 10^5 , 1 ≦ Q ≦ 10^5 的数据集,则进一步 给出 70 点。总共100点。

出力

输出由多行组成。 每次高桥君提问时,高桥君 如果您可以在 x_i 和城市 y_i 之间行驶偶数米 YES ,如果你不能动 在一行上输出 NO 。


入力例1

5 9
1 1 2 3
1 1 3 2
1 3 5 5
2 1 5 1
2 2 5 1
1 2 4 4
1 1 4 6
2 1 5 1
2 3 5 1

出力例1

NO
YES
YES
YES

每个问题发生时的城市和道路状况如下。 左边是 1, 2 右边的情况来自第二个问题。 3, 4 这就是我问第二个问题时发生的情况。

2 关于第二个问题, 如果您按照 2, 1, 3, 5 的顺序行驶,则行驶的总距离将为 10 。

3 关于第二个问题, 如果您按照 1, 4, 2, 1, 3, 5 的顺序行驶,则行驶的总距离将为 20 。

4 关于第二个问题, 如果您按照 3, 1, 2, 4, 1, 3, 5 的顺序行驶,则行驶的总距离将为 22 。


入力例2

5 7
1 1 2 3
1 2 4 4
1 5 3 1
2 1 3 1
2 5 3 1
1 3 1 2
2 3 4 1

出力例2

NO
NO
NO

1 第二个问题时,城市 1 从市区出发 无法到达 3 。因此答案是 NO 。


入力例3

3 6
1 1 2 1
1 1 3 3
1 2 3 2
1 2 1 2
2 1 3 1
2 2 3 1

出力例3

YES
YES

相同 2 请注意,一个城市可以有多条道路。