Submit | All submissions | Best solutions | Back to list |

## MMCUT - Tree cut |

You are given a tree (a connected, acyclic graph) along with a set of **commodities**, i.e. pairs of vertices, (*s _{1}*,

*t*),...,(

_{1}*s*,

_{m}*t*) (

_{m}*s*≠

_{i}*t*). A

_{i}**multicut**is a set of edges that when removed disconnects

*s*from

_{i}*t*for all

_{i}*i*. There is a unique path

*P*between every pair of vertices

_{u,v}*u,v*in a tree, and the

**max-cost**of a multicut

*S*is max

_{i}|

*S*∩

*P*|. You will be given a rooted tree of height

_{si, ti}*1*and a set of commodities and must return the minimum possible max-cost over all multicuts.

### Input

The first line of the input is "*N M*" (*1* ≤ *N, M* ≤ *100000*),
where *N* is the number of vertices in the tree and *M* is the number
of commodities. All vertices are numbered *0, ...,N-1*, and the
root has label *N - 1*. *M* lines then follow, where the *i*th line
is "*s _{i} t_{i}*", representing a commodity (

*s*,

_{i}*t*) where

_{i}*s*≠

_{i}*t*. Commodities are distinct: neither (

_{i}*s*,

_{i}*t*) = (

_{i}*s*,

_{j}*t*) nor (

_{j}*s*,

_{i}*t*) = (

_{i}*t*,

_{j}*s*) will hold when

_{j}*i*≠

*j*.

### Output

Your output should consist of a single number, the minimum possible max-cost of a multicut, followed by a newline.

### Example

Input:10 2 0 5 4 8Output:1

Added by: | Minilek |

Date: | 2007-10-25 |

Time limit: | 7.601s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP clisp LISP sbcl D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE |

Resource: | MIT Individual Contest 2007 |