Bob is going to make \(m\) trips on a tree. During each trip he goes from a node, \(x_{i}\), to another node, \(y_{i}\), using the simple path between the two nodes.
Alice is jealous of Bob, and doesn't want him to be able to go on any of the \(m\) trips. Before Bob wakes up, Alice plans to remove some edges in the tree, in a way that Bob wouldn't be able to make any of the \(m\) trips.
Please, help Alice find out the minimum number of edges she should remove from the tree, so Bob cannot make any of the trips.
INPUT FORMAT
The first line of input contains two integers, \(n\) \((2 <= n <= 15)\) and \(m\) \((1 <= m <= \frac{n(n - 1)}{2})\) - denoting the number of nodes in the tree, and the number of trips Bob wants to make.
The next \(n - 1\) lines each contain two integers, \(u_{i} (1 <= u_{i} <= n)\) and \(v_{i} (1 <= v_{i} <= n)\) (\(u_{i} < v_{i}\)) - denoting the edges in the tree.
The last \(m\) lines each contain two integers, \(x_{i} (1 <= x_{i} <= n)\) and \(y_{i} (1 <= y_{i} <= n)\) \((x_{i} \neq y_{i})\) - denoting start and end nodes of the trips Bob wants to make.
OUTPUT FORMAT
The minimum number of edges Alice should remove from the tree to make the trips impossible.
5 2 1 2 1 3 1 4 1 5 2 3 3 4
1
In the sample input we have a tree with \(4\) edges \((1, 2)\), \((1, 3)\), \((1, 4)\) and \((1, 5)\).
The tree looks like:
Bob wants to make the following trips 2 -> 3 and 3 -> 4.
It is easy to see that if we remove the edge \((1, 3)\), then he can't make any of those trips. The resulting graphs looks like:
Hence, the answer for this input is \(1\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor