Polish version    English version  
  History of OI -> XIII OI 2005/2006 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Stage III
Regulations
For contestants
Helpful resources
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN

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.

For the input data:
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
the correct outcome is:
13

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




Print friendly version