Bajtek is organizing a birthday party. There will be $n$ people, numbered from 1 to $n$. Some of these people already know each other, while others might be meeting for the first time. Bajtek has collected all the information about acquaintances in the form of a list of $m$ pairs of people who already know each other. The acquaintance relation is symmetric, which means that if person $i$ knows person $j$, then person $j$ knows person $i$.

Bajtek would like at least one group of four people to appear at the party such that all pairs of people in this group already know each other, except for exactly one pair; this way, that one pair will be able to get to know each other in pleasant company. More formally, Bajtek would like there to exist four (pairwise distinct) people $a, b, c, d$ such that exactly one of the pairs $\{a, b\}, \{a, c\}, \{a, d\}, \{b, c\}, \{b, d\}, \{c, d\}$ does not yet know each other. Help him determine if such people exist.

Input

The first line of input contains a single integer $t$ ($t \ge 1$) denoting the number of test cases.

The first line of each test case description contains two integers $n, m$ ($n \ge 1, m \ge 0$) denoting the number of people at the party and the number of acquaintance records, respectively. Each of the next $m$ lines of the description contains two integers $a_i, b_i$ ($1 \le a_i < b_i \le n$) denoting that persons $a_i$ and $b_i$ already know each other.

We guarantee that the pairs in the description do not repeat, i.e., for $i \neq j$, it holds that $a_i \neq a_j$ or $b_i \neq b_j$. Let $N$ be the sum of $n$ over all test cases, and $M$ be the sum of all $m$. It holds that $N, M \le 10^5$.

Output

For each test case, you should print one word TAK or NIE, indicating whether there exist four people satisfying the condition from the problem statement. If such people exist, then in the next line you should print any four integers $a, b, c, d$ satisfying this condition.

Examples

Input 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

Output 1

TAK
1 6 3 5
NIE

Note

In the first test case, among the pairs of people in the group $\{1, 6, 3, 5\}$, only the pair $\{1, 6\}$ does not know each other. In the second test case, in the only group of four that exists, everyone knows everyone else.