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