Counting Stars

Problem Description

We define a $k$-star graph $(k\ge 2)$ is a connected undirected graph with $k+1$ nodes and $k$ edges satisfies that all the $k$ edges are connected to a common node (and it's easy to show that this node is unique), and we call this node as the center of the star graph, and the other nodes are the leaves of the star graph. Now you are given a simple undirected graph with $n$ nodes and $m$ edges. Your task is to calculate how many $k$-star graphs are there in the given graph for all the integers $k \in [2,n-1]$ . Specifically, the problem can be described as follows: How many ways are there to choose a node $c$ and a set of $k$ nodes $\{l_1,l_2,\dots,l_k\}$ in the given graph, satisfies that there exists edges connected $c$ and each $l_i$ for all $i\in [1,k]$ in the given graph. Two star graphs are considered different if the center node $c$ is different or the set of leaves $\{l_1,l_2,\dots,l_k\}$ is different. Let $cnt_k$ represent the number of $k$-star graphs in the given graph module $10^9+7$ . You only need to print the bitwise XOR sum of all the $cnt_k$ (i.e. $cnt_2\oplus cnt_3\oplus\cdots\oplus cnt_{n-1}$ ,where $\oplus$ represents bitwise XOR).

Input

The first line of the input contains an integer $T\ (1\le T\le 5)$, indicating the number of the test cases. For each test case: The first line contains two integers $n,m\ (3\le n\le 10^6, 1\le m\le 10^6)$, indicating the number of nodes and edges in the given graph. Then the following $m$ lines, each line contains two integers $u,v\ (1\le u,v\le n, u\not =v)$ , indicating an edge in the given graph. It's guaranteed that the graph is simple.

Output

For each test case: print one line contains a single integer, indicating the bitwise XOR sum of all the $cnt_k$.

Sample Input

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

Sample Output

1
8

Hint

For the second sample, there are twelve $2$-star graphs and four $3$-star graphs, so the answer is $12\oplus 4 =8$. Note that the input scale is very large.

Source

2023“钉耙编程”中国大学生算法设计超级联赛（5）