Bobo 有一個包含 $n$ 個頂點同 $m$ 條邊嘅連通無向圖 $G$，頂點方便噉編號為 $1,2,\ldots,n$。

Bobo 揀一個非空嘅邊子集，令由所揀嘅邊組成嘅圖仍然連通。

佢想知道有幾多個咁嘅子集，答案對 $2$ 取模。

請注意，如果對任何兩個頂點 $a$ 同 $b$，都存在一條連接 $a$ 同 $b$ 嘅路徑，個圖就係連通嘅。

輸入格式

輸入包含零組或多組測試資料，以檔案結尾結束。對每組測試資料：

第一行有兩個整數 $n$ 同 $m$（$2 \le n \le 2 \cdot 10^5$，$1 \le m \le 2 \cdot 10^5$）。

之後 $m$ 行中嘅第 $i$ 行有兩個整數 $a_i$ 同 $b_i$，表示頂點 $a_i$ 同 $b_i$ 之間有一條邊。

保證所有 $m$ 嘅總和唔超過 $2 \cdot 10^5$，而且所有畀定嘅圖都係連通嘅。

輸出格式

對每組測試資料，輸出一個整數，表示對 $2$ 取模後嘅餘數。

樣例

輸入格式 1

2 1
1 2
3 2
1 2
2 3
3 3
1 2
2 3
3 1

輸出格式 1

1
1
0