Hiking Trails

After the apocalypse, during which every kind of natural disaster wreaked havoc across the earth, the remnants of human civilization have begun to rebuild. In its aftermath an unusual tourist industry arose: people explore the ruins of pre-disaster cities, scavenging for souvenirs of a bygone era. You work for the tourism board of what was once Los Angeles, and your job is to renovate the hiking trails that tourists use while exploring.

Each hiking trail connects two landmarks. The tourism board keeps a list of landmarks that it wants to be connected by trails. Some landmarks recently added to the list may not yet be connected to the trail network. Your task is to determine how to add the fewest trails so that every pair of landmarks is connected by a series of trails.

Because the trails are as interesting as the landmarks themselves, the board imposes one more rule: starting from any landmark, it must be possible to visit every landmark one or more times and return to the starting landmark while traveling along each trail exactly once. This is possible only when every landmark is connected to an even number of trails. All you need now is a program that computes the minimum number of trails to add so that these requirements are met.

Landmarks are numbered from 1 to L.

The first line contains the number K of data sets. K data sets follow, each in the format below.

The first line contains two integers L and T ($2 \le L \le 1000$, $1 \le T \le 5000$), where L is the number of registered landmarks and T is the number of already-existing trails. Landmarks are numbered from 1 to L. T lines follow, each containing two integers A and B ($1 \le A, B \le L$), indicating that a trail connects landmarks A and B. You may assume no trail connects a landmark to itself and that no two landmarks are connected by more than one trail. When adding new trails, however, you may add a trail between two landmarks that are already connected by a trail.

For each data set, output "Data Set x:" on a line by itself, where x is its number. On the next line, output the minimum number of trails that must be added to satisfy the requirements. Follow each data set with a blank line.