問題文
在高桥君居住的国家 有 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 请注意,一个城市可以有多条道路。