Bajtek 正在举办一场生日派对。派对上有 $n$ 个人，编号从 $1$ 到 $n$。其中一些人已经互相认识，而另一些人可能是第一次见面。Bajtek 收集了所有关于认识关系的信息，并以 $m$ 对已经认识的人的列表形式呈现。认识关系是对称的，这意味着如果人 $i$ 认识人 $j$，那么人 $j$ 也认识人 $i$。

Bajtek 希望派对上至少出现一组四个人，使得这四个人中恰好有一对人不认识，而其余所有对的人都已经认识；这样，这一对不认识的人就可以在愉快的氛围中互相结识。更正式地说，Bajtek 希望存在四个人（两两不同）$a, b, c, d$，使得在 $\{a, b\}, \{a, c\}, \{a, d\}, \{b, c\}, \{b, d\}, \{c, d\}$ 这六对关系中，恰好有一对人还不认识。请帮助他判断是否存在这样的人。

输入格式

输入的第一行包含一个整数 $t$ ($t \ge 1$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n, m$ ($n \ge 1, m \ge 0$)，分别表示派对上的人数和已知认识关系的数量。接下来的 $m$ 行，每行包含两个整数 $a_i, b_i$ ($1 \le a_i < b_i \le n$)，表示人 $a_i$ 和 $b_i$ 已经认识。

保证输入中的每一对关系不会重复，即对于 $i \neq j$，满足 $a_i \neq a_j$ 或 $b_i \neq b_j$。设 $N$ 为所有测试用例中 $n$ 的总和，$M$ 为所有测试用例中 $m$ 的总和。满足 $N, M \le 10^5$。

输出格式

对于每个测试用例，输出一行单词 TAK 或 NIE，表示是否存在满足题目条件的四个人。如果存在，则在下一行输出任意四个满足条件的整数 $a, b, c, d$。

样例

样例输入 1

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

样例输出 1

TAK
1 6 3 5
NIE

说明

在第一个测试用例中，在四个人 $\{1, 6, 3, 5\}$ 中，只有 $\{1, 6\}$ 这一对人不认识。在第二个测试用例中，唯一存在的四人组合中，每个人都互相认识。

子任务

测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。