F. Chaleur
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

DreamGrid has n friends which are conveniently numbered from 1 to n. They can be divided into two groups (possibly empty) such that:

  • Every pair of friends in the first group have to know each other.
  • Every pair of friends in the second group must not know each other.

Now, given the pairs of friends who know each other, DreamGrid would like to know the number of ways to find a group of friends with maximum size such that every pair of friends in the group have to know each other, and he would also like to know the number of ways to find a group of friends with maximum size such that every pair of friends in the group must not know each other.

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains two integers n and m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105) – the number of friends and the number of pairs of friends who know each other.

The i-th of the following m lines contains two integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi), which denotes that the ai-th friend and the bi-th friend know each other. Note that every unordered pair of (a, b) will appear at most once.

It is guaranteed that neither the sum of all n nor the sum of all m exceeds 2 × 106.

Output

For each test case, output two integers separated by a single space.

The first integer indicates the number of ways to find a group of friends with maximum size such that every pair of friends in the this group have to know each other.

The second integer indicates the number of ways to find a group of friends with maximum size such that every pair of friends in the group must not know each other.

Example
Input
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
Output
2 1
1 4
1 2