Bobo 有一个连通无向图 $G$，包含 $n$ 个顶点和 $m$ 条边，顶点编号为 $1, 2, \dots, n$。

Bobo 选择一个非空的边子集，使得由这些边构成的图仍然连通。他想知道满足条件的子集数量模 2 的结果。

注意，如果对于任意两个顶点 $a$ 和 $b$，都存在一条连接 $a$ 和 $b$ 的路径，则称该图是连通的。

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含两个整数 $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

输出格式 1

1

输入格式 2

3 2
1 2
2 3

输出格式 2

1

输入格式 3

3 3
1 2
2 3
3 1

输出格式 3

0