Leshphon was a peaceful and beautiful village in Byteland until the nasty disease came here. There are n districts in Leshphon, connected by m directed roads such that you can reach every other district from any district via these directed roads. In other words, it is strongly connected.
To control the sources of infection and cut off the channels of transmission, the government of Byteland decides to close exactly three directed roads in Leshphon, such that the village is not strongly connected anymore. There may be many possible solutions, can you figure out the total number of them?
The first line contains a single integer T (1≤T≤10), the number of test cases. For each test case:
The first line contains two integers n and m (3≤n≤50, 3≤m≤n(n−1)), denoting the number of districts and the number of roads.
Each of the following m lines contains two integers ui and vi (1≤ui,vi≤n, ui≠vi), describing a directed road from the ui-th district to the vi-th district.
It is guaranteed that the village is strongly connected, and all the given m roads are pairwise different.
1
4 7
1 2
2 3
3 4
4 1
1 3
2 4
3 134