AT_agc038_d [AGC038D] Unique Path

[problemUrl]: https://atcoder.jp/contests/agc038/tasks/agc038_d すぬけ君は、$ 0 $ から $ N-1 $ までの番号のついた $ N $ 個の頂点と、$ M $ 本の辺からなる無向グラフをお母さんにもらいました。 このグラフは連結で、また、多重辺や自己ループは存在しませんでした。 ある日、すぬけ君はこのグラフを壊してしまいました。 しかし、すぬけ君はこのグラフについて、$ Q $ 個の情報を覚えています。 $ i $ ($ 0\ \leq\ i\ \leq\ Q-1 $) 番目の情報は整数 $ A_i,B_i,C_i $ で表され、次のことを意味します。 - $ C_i=0 $ の時: 頂点 $ A_i $ から $ B_i $ に向かう単純パス（同じ頂点を $ 2 $ 度通らないパス）が、$ 1 $ つしか存在しない。 - $ C_i=1 $ の時: 頂点 $ A_i $ から $ B_i $ に向かう単純パスが $ 2 $ つ以上存在する。 すぬけ君は自分の記憶に自信がないので、これら $ Q $ 個の情報に合致するグラフが存在するのかどうか心配になりました。 すぬけくんの記憶に合致するグラフが存在するかどうか判定してください。

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ N-1\ \leq\ M\ \leq\ N\ \times\ (N-1)/2 $ - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ 0\ \leq\ A_i,B_i\ \leq\ N-1 $ - $ A_i\ \neq\ B_i $ - $ 0\ \leq\ C_i\ \leq\ 1 $ - 入力される値はすべて整数である。 ### Sample Explanation 1 例えば、辺集合が $ (0,1),(1,2),(1,4),(2,3),(2,4) $ であるグラフを考えると、これは条件を満たします。