代写program程序语言、代做Python，c++程序、代写Java编程-代写C/C++编程

Return to Problem List

Time Remaining: 1 hrs, 32 min, 26 sec

Not submitted yet

Bessie has a connected, undirected graph with vertices labeled and edges ( ).

may contain self-loops (edges from nodes back to themselves), but no parallel edges (multiple edges connecting the same

endpoints).

Let be a boolean function that evaluates to true if there exists a path from vertex to vertex that traverses exactly

edges for each and , and false otherwise. If an edge is traversed multiple times, it is included that many times in

the count.

Elsie wants to copy Bessie. In particular, she wants to construct an undirected graph such that for all and

Elsie wants to do the least possible amount of work, so she wants to construct the smallest possible graph. Therefore, your job is

to compute the minimum possible number of edges in .

Each input contains ( ) test cases that should be solved independently. It is guaranteed that the sum of over

all test cases does not exceed , and the sum of over all test cases does not exceed .

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of the input contains , the number of test cases.

The first line of each test case contains two integers and .

The next lines of each test case each contain two integers and ( ), denoting that there exists an edge

between and in .

Consecutive test cases are separated by newlines for readability.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, the minimum possible number of edges in on a new line.

SAMPLE INPUT:

In the first test case, Elsie can construct by starting with and removing . Or she could construct a graph with the

In each of these test cases, Elsie cannot do better than Bessie.

SCORING:

All test cases in input 3 satisfy .

All test cases in inputs 4-5 satisfy .

For all test cases in inputs 6-9, if it is not the case that for all , then there exists such that is

true and is false.

All test cases in inputs 10-15 satisfy .

Test cases in inputs 16-20 satisfy no additional constraints.