DreamGrid 有 $n$ 个朋友，编号从 $1$ 到 $n$。他们可以被分成两个组（可能为空），使得：

• 第一组中的每一对朋友都互相认识。
• 第二组中的每一对朋友都不互相认识。

现在，给定互相认识的朋友对，DreamGrid 想知道：有多少种方法可以找到一个最大规模的朋友组，使得该组中每一对朋友都互相认识；以及有多少种方法可以找到一个最大规模的朋友组，使得该组中每一对朋友都不互相认识。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^5, 0 \le m \le 10^5$)，分别表示朋友的数量和互相认识的朋友对数。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，表示第 $a_i$ 个朋友和第 $b_i$ 个朋友互相认识。注意，每一对无序对 $(a, b)$ 最多出现一次。

保证所有测试数据的 $n$ 之和与 $m$ 之和均不超过 $2 \times 10^6$。

输出格式

对于每组测试数据，输出两个由空格分隔的整数。

第一个整数表示找到最大规模的朋友组（使得组内每一对朋友都互相认识）的方法数。

第二个整数表示找到最大规模的朋友组（使得组内每一对朋友都不互相认识）的方法数。

样例

样例输入 1

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

样例输出 1

2 1
1 4
1 2