Bobo は、頂点数が $n$、辺数が $m$ の連結な無向グラフ $G$ を持っています。頂点には便宜上 $1,2,\ldots,n$ の番号が付いています。

Bobo は、選んだ辺からなるグラフが依然として連結になるように、空でない辺の部分集合を選びます。そのような部分集合の個数を $2$ で割った余りを求めたいと考えています。

任意の 2 頂点 $a,b$ の間にそれらを結ぶ道が存在するとき、グラフは連結であるといいます。

入力

入力には 0 個以上のテストケースが含まれ、ファイルの終端で終了します。各テストケースについて、次の形式で与えられます。

最初の行には 2 つの整数 $n,m$（$2 \le n \le 2 \cdot 10^5$、$1 \le m \le 2 \cdot 10^5$）が与えられます。

続く $m$ 行のうち $i$ 行目には、頂点 $a_i$ と $b_i$ を結ぶ辺を表す 2 つの整数 $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