In the mathematical discipline of graph theory, the line graph of a simple undirected graph $$$G$$$ is another simple undirected graph $$$L(G)$$$ that represents the adjacency between every two edges in $$$G$$$.
Precisely speaking, for an undirected graph $$$G$$$ without self-loops or multiple edges, its line graph $$$L(G)$$$ is a graph such that
Figure: Generation of the Line Graph Given a simple undirected graph $$$G$$$, you need to find the minimum number of vertices among all the graphs in sequence $$$L^0(G), L^1(G), \ldots, L^{k-1}(G)$$$, where $$$L^0(G)=G$$$ and $$$L^t(G)=L(L^{t-1}(G))$$$ for each positive integer $$$t$$$.
The input contains several test cases, and the first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^5$$$), denoting the number of test cases.
For each test case:
The first line contains three integers $$$n$$$ ($$$1 \le n \le 10^5$$$), $$$m$$$ ($$$0 \le m \le \min\left(\frac{n(n-1)}{2}, 10^5\right)$$$)), and $$$k$$$ ($$$1 \le k \le 10^5$$$), denoting the number of vertices and edges in graph $$$G$$$ and the length of the line graph sequence.
Then $$$m$$$ lines follow, each of which contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), denoting an undirected edge connecting the $$$u$$$-th and the $$$v$$$-th vertices in graph $$$G$$$. It is guaranteed that graph $$$G$$$ contains no self-loops or multiple edges.
It is guaranteed that the total number of vertices and edges in all test cases do not exceed $$$10^5$$$ respectively.
For each test case, output a line containing a single integer, indicating the minimum number of vertices among all the graphs in the sequence $$$L^0(G), L^1(G), \ldots, L^{k-1}(G)$$$.
45 5 31 21 31 42 54 55 4 31 21 31 41 55 4 31 22 33 44 55 0 3
5430
