畀定一個冇自環、冇重邊嘅無向圖。

為圖入面嘅每個頂點賦予一個非負整數權值。如果一種賦值方案滿足以下兩個條件，就稱之為合法嘅：

• 任意兩個相鄰頂點嘅權值恰好相差 $1$；
• 如果某個頂點嘅權值嚴格細過佢所有鄰居嘅權值，噉佢嘅權值就等於 $0$。

求合法賦值方案嘅數量，對 $998\,244\,353$ 取模。如果存在某個頂點喺兩種賦值方案入面嘅權值唔同，就認為呢兩種賦值方案唔同。

輸入格式

第一行包含一個整數 $t$，表示測試數據嘅組數。

每組測試數據嘅第一行包含兩個整數 $n$ 同 $m$（$2 \le n \le 10^6$，$1 \le m \le 10^6$），分別表示圖入面嘅頂點數同邊數。

接住落嚟嘅 $m$ 行，每行包含兩個整數 $u$ 同 $v$（$1 \le u, v \le n$，$u \ne v$），表示對應邊嘅兩個端點。圖入面唔包含自環或者重邊。每個頂點至少有一個鄰居。

所有測試數據入面 $m$ 嘅總和唔超過 $10^6$。

輸出格式

對於每組測試數據，輸出一個整數，表示合法賦值方案嘅數量對 $998\,244\,353$ 取模嘅結果。

樣例

輸入格式 1

2
4 3
1 2
2 3
3 4
3 3
1 2
2 3
1 3

輸出格式 1

6
0