Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$, denoting the number of houses and the number of roads ($2 \le n \le 10^5$; $n - 1 \le m \le 2 \cdot 10^5$).

Each of the following $m$ lines contains two integers $u$ and $v$, describing a bidirectional road between houses $u$ and~$v$ ($1 \le u, v \le n$; $u \ne v$). No two houses are connected by more than one road. It is possible to get from any house to any other one using the roads.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$, and the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$.