D - 偶数メートル Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋くんの住む国には 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行に出力せよ。

入力例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 つの街に複数本の道路が敷設され得ることに注意してください。