Squid Game solution codeforces
After watching the new over-rated series Squid Game, Mashtali and Soroush decided to hold their own Squid Games! Soroush agreed to be the host and will provide money for the winner’s prize, and Mashtali became the Front Man!
kill eliminate all the players so he could take the money for himself!players registered to play in the games to win the great prize, but when Mashtali found out how huge the winner’s prize is going to be, he decided to
Here is how evil Mashtali is going to eliminate players: Squid Game solution codeforces
There is an unrooted tree withvertices. Every player has special vertices and .
In one operation, Mashtali can choose any vertexof the tree. Then, for each remaining player he finds a vertex on the simple path from to , which is the closest to . If and , player will be eliminated.
Now Mashtali wondered: “What is the minimum number of operations I should perform so that I can remove every player from the game and take the money for myself?” Squid Game solution codeforces
Since he was only thinking about the money, he couldn’t solve the problem by himself and asked for your help!
The first line containsinteger and — the number of vertices of the tree and the number of players.
The second line containsintegers — denoting an edge between node and .
The-th of the following lines contains two integers and — the special vertices of the -th player.
Print the minimum number of operations Mashtali has to perform.
If there is no way for Mashtali to eliminate all the players, print.
6 3 1 1 1 4 4 1 5 3 4 2 6
output Squid Game solution codeforces
input Squid Game solution codeforces
5 3 1 1 3 3 1 2 1 4 1 5
Explanation for the first sample: