Tribal War

On a certain planet live $N$ small tribes. For convenience, number the tribes from $1$ to $N$.

• Any two distinct tribes are either allied or hostile. This relation is symmetric, so there is no case where tribe A considers tribe B an ally while B considers A an enemy.
• Even if tribe A and tribe B are allied and tribe B and tribe C are allied, tribe A and tribe C may be hostile.
• For any three distinct tribes, if all three are allied, call it a three-way alliance, and if all three are hostile, call it a three-way hostility.

Find the total number of distinct three-way alliances and three-way hostilities among the $N$ tribes.

For example, suppose $N = 5$, tribes 1 and 2, tribes 1 and 3, and tribes 4 and 5 are allied, and every other pair of tribes is hostile. Then $(2, 3, 4)$ and $(2, 3, 5)$ form three-way hostilities and there is no three-way alliance, so the answer is $2$.

As another example, suppose $N = 5$ and tribes 1 and 2, tribes 2 and 3, and tribes 1 and 3 are allied. Then $(1, 2, 3)$ is a three-way alliance, and $(1, 4, 5)$, $(2, 4, 5)$, $(3, 4, 5)$ are three-way hostilities, so the answer is $4$.

The first line gives the number of test cases $T$. ($1 \le T \le 10$)

The first line of each test case gives $N$ and $M$, separated by a space.

The next $M$ lines each give two integers $x$ and $y$, meaning that $x$ and $y$ are allied.

Every alliance given in the input satisfies $1 \le x < y \le N$, and the same pair of tribes is never given more than once.

A pair of tribes that does not appear in the input is assumed to be hostile.

For each test case, print the alliance-antialliance coefficient on one line.