給定一個無自環、無重邊的無向圖。

為圖中的每個頂點賦予一個非負整數權值。如果一種賦值方案滿足以下兩個條件，則稱其為合法的：

• 任意兩個相鄰頂點的權值恰好相差 $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