Subway

Memory limit: 128 MB

A certain city has been coping with subway construction for a long time. The finances have been mismanaged and the costs have been underestimated to such extent that no funds were foreseen for the purchase of trains. As a result, too many stations and only some of the planned tunnels have been built - barely enough to allow a connection between any two stations to exist. The number of tunnels (each of them is bidirectional) is one less than the number of stations built. From the remaining funds only a handful of trains have been acquired.

To save their face the board of directors have asked you to plan subway routes in such a way as to allow maximal number of stations to be connected. Each train travels on a specified route. The routes cannot branch (no three tunnels starting at a single station may belong to the same route). Distinct routes may comprise the same station or tunnel.

Task

Write a programme which:

• reads a description of the tunnel system and the number of subway lines, which are to be planned from the standard input,
• calculates the maximal number of stations which can be covered by the specified number of subway lines,
• writes the outcome to the standard output.

Input

The first line of the standard input contains two integers and (, ) separated by a single space. The number denotes the number of stations and the number denotes the number of subway lines, which are to be planned. The stations are numbered from 1 to .

Each of the following lines contains two distinct integers separated by a single space. The numbers in the -th line denote the numbers of stations connected by -th tunnel.

Output

The first and only line of the standard output should contain a single integer denoting the maximal number of stations which can be covered by train routes.

17 3
1 2
3 2
2 4
5 2
5 6
5 8
7 8
9 8
5 10
10 13
13 14
10 12
12 11
15 17
15 16
15 10

13

The figure represents the tunnel system (with subway routes marked) in one of the optimal configurations.

Print friendly version