最近，Byteasar 发现了在 Bytotia 旅行的乐趣。该国有 $n$ 个城镇（为了方便起见，编号为 $1$ 到 $n$），Byteotian 铁路在某些城镇对之间运营着 $m$ 条双向直达铁路线。利用这些线路，Byteasar 可以到达 Bytotia 的任何城镇，尽管他可能需要换乘。

我们的主人公特别喜欢那些从同一个城市出发并回到该城市，且除了起点和终点外不经过任何其他城市，也不重复使用任何连接的旅程。Byteasar 将这样的旅程称为“有趣的”。

在最近的多次旅行中，Byteasar 注意到他迄今为止所有有趣的旅程都使用了相同数量的铁路线。他怀疑这并非巧合，而是 Bytotia 铁路网络的一个普遍属性，并请求你验证这一假设。此外，如果该论点成立，他还想知道所有可能的有趣旅程的数量。无论出于何种原因，他不需要确切的数量，只需要该数量除以 $10^9 + 7$ 的余数。

旅程可以正式描述为依次访问的城镇编号序列。如果两个长度相同的旅程在某个索引 $i$ 处第 $i$ 个城镇不同，则它们是不同的；旅程的长度是它所使用的铁路线数量。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$ ($n \ge 1, m \ge 0$)，由单个空格分隔，分别指定了 Bytotia 的城镇数量和铁路线数量。接下来有 $m$ 行，描述铁路线。其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，由单个空格分隔，表示城镇 $a_i$ 和 $b_i$ 之间存在一条双向铁路线。每对城镇之间最多只有一条直接连接。

输出格式

如果（不幸的是）根本不存在有趣的旅程，则应向标准输出打印单词 BRAK（波兰语，意为“无”）。如果存在这样的旅程，但它们的长度不全相同（反驳了 Byteasar 的假设），则应向标准输出打印单词 NIE（波兰语，意为“否”）。最后，如果所有有趣的旅程长度都相同（即假设成立），则应向标准输出打印单词 TAK（波兰语，意为“是”），并在下一行打印两个由单个空格分隔的整数：此类旅程的共同长度及其数量对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

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

样例输出 1

TAK
3 12

说明 1

共有 12 条有趣的旅程，长度均为 3。它们是：1-2-3-1, 1-3-2-1, 2-1-3-2, 2-3-1-2, 3-1-2-3, 3-2-1-3, 1-4-5-1, 1-5-4-1, 4-1-5-4, 4-5-1-4, 5-1-4-5, 5-4-1-5。

样例输入 2

12 14
1 2
2 4
3 1
4 3
4 5
5 6
6 7
7 8
8 4
7 9
9 12
12 11
11 10
10 6

样例输出 2

NIE

子任务

测试集由以下子集组成。在每个子集中，可能有多个测试组。