在 ICPCCamp 中有 $n$ 座城市，编号为 $1, 2, \dots, n$。此外还有 $m$ 条双向道路：第 $i$ 条道路连接城市 $a_i$ 和 $b_i$。

Bobo 选择一个非空的城市子集组成一个联盟。对于联盟中的任意两座城市 $a$ 和 $b$，必须存在一条从 $a$ 到 $b$ 的路径，且该路径不经过联盟之外的任何城市。换句话说，该联盟必须是连通的。

Bobo 想知道有多少种选择这样的子集的方法，但他害怕数字太大。因此，他只想求出这个方案数模 2 的结果。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 50, 0 \le m \le \frac{n(n-1)}{2}$)。

接下来 $m$ 行，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n, 0 < |a_i - b_i| \le 13$)。

输出格式

输出一个整数，表示可能的子集数量模 2 的结果。

样例

输入 1

3 2
1 2
2 3

输出 1

0

输入 2

3 3
1 2
2 3
3 1

输出 2

1