TASK
1 - CPU
John is attempting to
design a low cost processor that he can build on a circuit board using standard
components. The components need to be connected together with connecting wires
("connections"). The connections cannot cross components or each
other, but do not have to follow straight lines.
John has already made the
basic design, in which all the components are connected together in a loop
(called the main loop). The components in the main loop are in a consecutive
order. However, to speed up the processor he wants to add direct connections
between some pairs of components. For each component he will wish to add at
most one connection. He has made a list of all the connections he wants to add,
and has ordered them by importance. He will incorporate the K most important of these connections,
where K is as large as
possible without forcing wires to cross. Your task is to write a program and
help John to determine the largest possible value of K .
Input
Your program should read
the input from a file "cpu.in". The first line of the file contains
an integer N (where 1 ≤
N ≤ 200.000)
representing the number of components that John has already in the main loop.
The second line contains an integer M (where
1 ≤ M ≤ 50.000)
representing the number of extra connections that John is considering to add.
The remaining M lines contain
two positive integers P and Q ,
indicating that John wishes to connect P to
Q .
Note : there is never a connection from a component
to itself, although a component may be connected to an adjacent component in
the main loop. The connections are listed in descending order of importance.
Output
Your program should write
the output into a file "cpu.out" with 1 line containing a single
integer, the maximum possible value of K .
Example
|
cpu.in |
cpu.out |
Format : In both input and output files, all numbers in
a line are separated with a single space and all lines terminate with a newline
character.