407346: GYM102769 F Friendly Group

Professor Alex will organize students to attend an academic conference.

Alex has $$$n$$$ excellent students, and he decides to select some of them (possibly none) to attend the conference. They form a group. Some pairs of them are friends.

The friendly value of the group is initially $$$0$$$. For each couple of friends $$$(x,y)$$$, if both of them attend the conference, the friendly value of the group will increase $$$1$$$, and if only one of them attends the conference, the friendly value of the group will decrease $$$1$$$. If $$$k$$$ students attend the conference, the friendly value of the group will decrease $$$k$$$.

Alex wants to make the group more friendly. Please output the maximum friendly value of the group.

The first line of the input gives the number of test cases, $$$T\ (1 \le T \le 10^4)$$$. $$$T$$$ test cases follow.

For each test case, the first line contains two integers $$$n\ (1 \le n \le 3 \times 10^5)$$$ and $$$m\ (1 \le m \le 10^6)$$$, where $$$n$$$ is the number of students and $$$m$$$ is the number of couples of friends.

Each of the following $$$m$$$ lines contains two integers $$$x_i,y_i\ (1 \le x_i ,y_i \le n, x_i \not= y_i)$$$, representing student $$$x_i$$$ and student $$$y_i$$$ are friends. It guaranteed that unordered pairs $$$(x_i,y_i)$$$ are distinct.

The sum of $$$n$$$ in all test cases doesn't exceed $$$10^6$$$, and the sum of $$$m$$$ in all test cases doesn't exceed $$$2 \times 10^6$$$.

For each test case, output one line containing "Case #x: y", where $$$\texttt{x}$$$ is the test case number (starting from $$$1$$$), and $$$\texttt{y}$$$ is the maximum friendly value of the group.

2
4 5
1 2
1 3
1 4
2 3
3 4
2 1
1 2

Case #1: 1
Case #2: 0