APIO '10 P2 - Patrol

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

In a city, there are villages numbered . There are roads connecting them. Each road connects exactly villages, and from any village, one can reach any other village using these roads. The length of each road is unit.

To ensure safety of the people in the city, each day a city police patrol has to travel on every road. The police station is at village , so the patrol has to start from village 1 and finally return to village at the end of the day.

Consider the following example of a city with villages below. Villages are shown as circles and village is shown as a black circle. The roads are the lines connecting these villages. To traverse all roads, the patrol has to travel units each day. Note that the patrol must travel along each road twice to complete each day’s job.

To reduce the total distance required, the city plans to build new shortcuts between these villages. Each shortcut can connect any two villages. Two shortcuts can end at the same village (see example (c) below). A shortcut can even be a loop; that is, connect a village to itself.

Funding is limited, so is either or . Also, to make sure that the city is not wasting money, it is required that the patrol must travel along each shortcut exactly once a day.

Consider the following examples.

In example (a), one shortcut is built, and the total distance is . In example (b), two shortcuts are built, and the total distance the patrol has to travel is . In the last example (c), two shortcuts are built, however since there is a requirement on the number of times the patrol can travel on each shortcut exactly once, the total distance now becomes .

Write a program that reads the information about the roads between the villages and the number of shortcuts to be built and computes the location for the shortcuts that minimizes the total distance the patrol has to travel each day.

Input Specification

The first line of input contains two integers and . The next lines contain information about the roads. Each of these lines contains two integers and , , which says that there is a road connecting village and village .

Output Specification

Your program should output one line with an integer which is the minimum distance the patrol has to travel after shortcuts have been built.

Sample Input 1

8 1
1 2
3 1
3 4
5 3
7 5
8 5
5 6

Sample Output 1

11

Sample Input 2

8 2
1 2
3 1
3 4
5 3
7 5
8 5
5 6

Sample Output 2

10

Sample Input 3

5 2
1 3
2 3
3 4
4 5

Sample Output 3

6

Constraints

• In of the test cases, and .
• In of the test cases, .
• In of the test cases, the maximum number of adjacent villages for each village is at most .
• In of the test cases, the maximum number of adjacent villages for each village is at most .
• In of the test cases, and .

Comments

• Paradox  commented on Sept. 1, 2017, 5:11 p.m.

Why does Sample Input 1 contain loops?

• Kirito  commented on Sept. 2, 2017, 11:48 p.m. edited

This comment is hidden due to too much negative feedback. Click here to view it.