We define a k-star graph (k ≥ 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 ∈ [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 {l1, l2, . . . , lk} in the given graph, satisfies
that there exists edges connected c and each li for all i ∈ [1, k] in the given graph. Two star graphs are
considered different if the center node c is different or the set of leaves {l1, l2, . . . , lk} is different.
Let cntk represent the number of k-star graphs in the given graph module 109 + 7 .
You only need to print the bitwise XOR sum of all the cntk (i.e. cnt2 ⊕ cnt3 ⊕ · · · ⊕ cntn−1 ,where ⊕
represents bitwise XOR).
输入格式
The first line of the input contains an integer T (1 ≤ T ≤ 5), indicating the number of the test cases.
For each test case:
The first line contains two integers n, m (3 ≤ n ≤ 106
, 1 ≤ m ≤ 106
), indicating the number of nodes and
edges in the given graph.
Then the following m lines, each line contains two integers u, v (1 ≤ u, v ≤ n, u 6= v) , indicating an edge
in the given graph. It’s guaranteed that the graph is simple.
输出格式
For each test case: print one line contains a single integer, indicating the bitwise XOR sum of all the cntk.
输入样例
复制
2
3 2
1 2
2 3
4 6
1 2
1 3
1 4
2 3
2 4
3 4
输出样例
复制
1
8
数据范围与提示
For the second sample, there are twelve 2-star graphs and four 3-star graphs, so the answer is 12 ⊕ 4 = 8.
Note that the input scale is very large.