Bears and Bees

All submissions for this problem are available.

It's a very funny thought that, if Bears were Bees, They'd build their nests at the bottom of trees. And that being so (if the Bees were Bears), We shouldn't have to climb up all these stairs. Winnie-the-Pooh, a Complaining Song

Have you ever thought, when given an undirected graph in some problem, that it would be easier to solve it if the graph's edges were actually its vertices and the graph's vertices were its edges? This problem is right about this -- unfortunately, not about bears and bees (but if you want, you may think of vertices as of bears and of edges as of bees (or even vice versa)).

Suppose you're given an undirected graph G₀ with N vertices and M edges. Let's perform a simple transformation on graph G₀ to obtain graph G₁ with M vertices so that each vertex of G₁ corresponds to a unique edge of G₀ and a pair of vertices in G₁ is connected by a single edge if and only if the corresponding edges of G₀ share a common vertex. Similarly, let's perform a simple transformation on graph G₁ to obtain graph G₂, and let's perform a simple transformation on graph G₂ to obtain graph G₃.

All you have to do is to output the number of vertices and edges in G₃.

Input

The first line of the input file contains one integer T -- the number of test cases (no more than 10). Each test case is described by a line containing two integers N and M (1 ≤ N, M ≤ 1000) followed by M lines, each containing two integers between 1 and N, inclusive, separated by a single space and describing an edge of graph G₀. It's guaranteed that each edge connects two distinct vertices and each pair of vertices is directly connected by at most one edge.

Output

For each test case output just one line containing two integers -- the number of vertices and edges in G₃.

Example

Input:
2
3 3
1 2
1 3
2 3
4 4
1 2
1 3
2 3
3 4

Output:
3 3
8 18

Explanation:

In the first test case the given graph is a "triangle". It's easy to see that a simple transformation on a triangle results in the same triangle (as it contains three pairwise connected vertices and three pairwise "connected" edges).

---

Date:	2012-01-17
Time limit:	2s
Source limit:	50000B
Languages:	All