AT_arc036_d [ARC036D] 偶数メートル

[problemUrl]: https://atcoder.jp/contests/arc036/tasks/arc036_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 $ つの街に複数本の道が敷かれることがある。 - 高橋くんが質問した時点では、それ以前の入力の全ての道路の敷設が完了されているものとする。

出力は複数行からなる。 高橋くんが質問するたびに、高橋くんが街 $ x_i $ と街 $ y_i $ の間を偶数メートルで移動できるならば `YES` 、移動できないならば `NO` と1行に出力せよ。

### 部分点 この問題には部分点が設定されている。 - $ 1\ ≦\ N\ ≦\ 3,000\ ,\ 1\ ≦\ Q\ ≦\ 3,000 $ を満たすデータセットに正解した場合は $ 30 $ 点が与えられる。 - $ 1\ ≦\ N\ ≦\ 10^5\ ,\ 1\ ≦\ Q\ ≦\ 10^5 $ を満たすデータセットに正解した場合はさらに $ 70 $ 点が与えられる。合計で$ 100 $点となる。 ### Sample Explanation 1 各質問時点での街と道路の様子は以下のようになります。 左が $ 1,\ 2 $ つ目の質問の時の様子で、右が $ 3,\ 4 $ つ目の質問の時の様子です。 !\[\](/img/arc/036/Dsample1.png) $ 2 $ つ目の質問に対しては $ 2,\ 1,\ 3,\ 5 $ という順に道路を進むと移動距離の合計が $ 10 $ になります。 $ 3 $ つ目の質問に対しては $ 1,\ 4,\ 2,\ 1,\ 3,\ 5 $ という順に道路を進むと移動距離の合計が $ 20 $ になります。 $ 4 $ つ目の質問に対しては $ 3,\ 1,\ 2,\ 4,\ 1,\ 3,\ 5 $ という順に道路を進むと移動距離の合計が $ 22 $ になります。 ### Sample Explanation 2 $ 1 $ つ目の質問の時点では、そもそも街 $ 1 $ から街 $ 3 $ に行く方法がありません。よって答えは `NO` になります。 ### Sample Explanation 3 同じ $ 2 $ つの街に複数本の道路が敷設され得ることに注意してください。