Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Ideal Frame
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 183Accepted: 54


Peter is fond of collecting various funny things. He can spend hours restoring and polishing some useless item he had found in a garbage heap.

Recently he has found a really nice thing. It is a small metal construction that consists of several iron rods soldered together with little tin beads. An example of such construction is shown on the picture below.

Peter has immediately understood that these nice rods are exactly what he needs for the frame around the photo of his girlfriend. The frame must have a form of a closed chain of rods. To do the transformation Peter would unsolder some beads, releasing the rods ends, and after that solder some free rod ends together again. When unsoldering a bead, Peter can separate the ends of the rods connected at that bead, in arbitrary way — that is, he can choose an arbitrary partition of rods connected to the bead into non-empty groups, so that once the bead is unsoldered only the rods belonging to the same group remain connected to each other.

For example, to turn the construction on the picture above to a frame, he could unsolder the bead A, separating the end of rod 1, unsolder the bead D, separating pairs or rods 4–5 and 3–7 (but keeping the rods in pairs connected), and unsolder the bead E, separating the end of the rod 7. After that he needs to solder the free ends of rods 1 and 7 to get the frame 1–7–3–2–4–5–6–8.

Now help Peter to find the way to create the frame from the construction he has got by making as few operations as possible. There are two types of operations: unsoldering a bead, and soldering two free ends of rods together. Unsoldering is counted as one operation no matter how many rods were connected in a bead and how they were rearranged.


The first line of the input file contains two integer numbers n and m — the number of beads and the number of rods, respectively (0 ≤ n1 000, 2 ≤ m50 000). Let the beads be numbered from 1 to n. The following m lines contain two integer numbers each — the numbers of the beads connected by the corresponding rod. If the end of the rod is not connected to any bead, 0 is used.

The construction may be not connected (i.e. it can consist of several pieces). There can be beads that have only one rod soldered into it. These beads need not be unsoldered before the corresponding end of the rod is soldered to another one.

There can also be beads that have no rods soldered into it. Since Peter is only interested in rods, these beads need not be soldered/unsoldered.


Output one integer number — the number of operations Peter needs to create the frame from the construction described in the input file.

Sample Input

#16 8
1 2
1 3
3 4
1 4
4 6
5 6
4 5
1 5
#20 2
0 0
0 0
#33 3
0 1
0 0
2 2

Sample Output



Northeastern Europe 2006, Northern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator