在 Bajtex 公司的内部网络中，有 $n$ 个路由器，编号从 $1$ 到 $n$。一些路由器对之间由双向链路连接。每条链路连接两个不同的路由器，且任意两个路由器之间最多只有一条直接链路。任意两个路由器之间至少存在一条路径相连。

系统管理员正在部署一种新的数据包路由算法。这要求为每个路由器 $a$ 分配一个唯一的 32 位路由代码 $K(a)$（$0 \le K(a) < 2^{32}$，$K(a) \neq K(b)$，当 $a \neq b$ 时）。如果两个路由器通过直接链路相连，则其中一个代码应为另一个代码的一半（向下取整）。换句话说，如果路由器 $a$ 和 $b$ 由一条链路连接，则：

$$K(a) = \left\lfloor \frac{K(b)}{2} \right\rfloor \quad \text{或} \quad K(b) = \left\lfloor \frac{K(a)}{2} \right\rfloor$$

请检查是否可以按照这些要求分配路由代码。如果可以，请计算这些代码的最小可能总和 $\sum_{i=1}^n K(i)$。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 200\,000$，$n - 1 \le m \le 200\,000$），分别表示路由器的数量和链路的数量。

接下来的 $m$ 行描述链路。第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$，$a_i \neq b_i$），描述路由器 $a_i$ 和 $b_i$ 之间的一条链路。每条链路在输入中最多出现一次（如果 $i \neq j$，则 $(a_i, b_i) \neq (a_j, b_j)$ 且 $(a_i, b_i) \neq (b_j, a_j)$）。

输出格式

如果可以正确分配唯一的路由代码，输出一个整数：代码的最小可能总和 $\sum_{i=1}^n K(i)$。如果无法分配，则仅输出单词 NIE。

样例

样例输入 1

4 3
1 2
1 3
1 4

样例输出 1

6

样例输入 2

4 6
1 2
2 3
3 4
4 1
1 3
2 4

样例输出 2

NIE

说明

在第一个样例中，路由器可以分别分配代码：$1, 0, 2, 3$，其总和为 $6$。 在第二个样例中，无法分配代码。