問題文

$N$ 人の参加者を $2$ つのチームに分けます。 $Q$ 個の要望があり、$i$ 番目の要望は $t_i, a_i, b_i$ で表されます。

$t_i = 0$ のとき参加者 $a_i$ と $b_i$ は同じチーム、 $t_i = 1$ のとき異なるチームでなければなりません。

すべての要望を満たす分け方が何通りあるかを $998244353$ で割った余りで求めてください。 要望を満たす分け方が存在しない場合は $0$ を出力してください。

なお、どちらかのチームが空になっても構いません。 また、$2$ つのチームは区別します。

入力

$N\ Q$
$t_1\ a_1\ b_1$
$\vdots$
$t_Q\ a_Q\ b_Q$

• $1 \le N \le 2 \times 10^5$
• $0 \le Q \le 2 \times 10^5$
• $t_i$ は $0$ または $1$
• $1 \le a_i \lt b_i \le N$
• 入力はすべて整数

出力

要望をすべて満たす分け方の個数を $998244353$ で割った余りを出力してください。 最後に改行してください。

サンプル

4 2
0 1 2
1 3 4

4

3 3
0 1 2
1 2 3
0 1 3

0