题目描述

题目译自 XXXII Olimpiada Informatyczna – III etap Impreza

Bajtek 正筹备一场盛大的生日派对，邀请了 $n$ 位宾客，编号从 $1$ 到 $n$。这些宾客中，有些已相互认识，有些可能是初次见面。Bajtek 精心收集了所有熟人关系，整理出 $m$ 对已认识的宾客名单。熟人关系是对称的，即若宾客 $i$ 认识宾客 $j$，则宾客 $j$ 也认识宾客 $i$。

Bajtek 希望派对上能出现至少一组四人，满足这样的条件：这四人中，除了一对宾客尚未认识外，其他所有两人组合都已熟识。如此，这对新朋友就能在友好的氛围中结识。更正式地说，他希望找到四个互不相同的宾客 $a, b, c, d$，使得集合 $\{a, b\}, \{a, c\}, \{a, d\}, \{b, c\}, \{b, d\}, \{c, d\}$ 中恰好有一对尚未认识。你的任务是帮助 Bajtek 判断是否存在这样的四人组，若存在，则提供一组符合条件的宾客编号。

输入格式

第一行包含一个整数 $t$ $(t \geq 1)$，表示测试数据数量。

每组测试数据描述如下：

• 第一行包含两个整数 $n, m$ $(n \geq 1, m \geq 0)$，分别表示派对宾客人数和熟人关系对数。
• 接下来的 $m$ 行，每行包含两个整数 $a_i, b_i$ $(1 \leq a_i < b_i \leq n)$，表示宾客 $a_i$ 和 $b_i$ 已认识。 保证熟人关系对不重复，即对于 $i \neq j$，有 $(a_i, b_i) \neq (a_j, b_j)$。

令 $N$ 为所有测试数据中 $n$ 之和，$M$ 为所有 $m$ 之和，满足 $N, M \leq 10^5$。

输出格式

对于每组测试数据，输出一行，包含一个字符串 TAK 或 NIE，表示是否存在满足条件的四人组。若为 TAK，则在下一行输出四个整数 $a, b, c, d$，表示一组符合条件的四人。若存在多种解，输出任意一种。

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

TAK
1 6 3 5
NIE

在第一组数据中，在四人组 $\{1, 6, 3, 5\}$ 中，仅 $\{1, 6\}$ 尚未认识，其他对均已熟识，满足条件。第二组数据中，唯一可能的四人组 $\{1, 2, 3, 4\}$ 中，所有对均已认识，无法满足恰有一对不认识的条件。

附加样例

1. 六组测试用例，每个 $n=4, m=5$，答案均为 TAK。
2. 一组测试用例，$n=1000, m=0$，答案为 NIE。
3. 一组测试用例，$n=400$，每对宾客均认识，答案为 NIE。
4. 一组测试用例，$n=m=10^5$，对于每个 $i < n$，宾客 $i$ 认识 $i+1$，且宾客 $1$ 认识 $n$，答案为 NIE。

数据范围与提示

详细子任务附加限制及分值如下表所示。