Squid Game solution codeforces

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!

𝑚m 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 kill eliminate all the players so he could take the money for himself!

Here is how evil Mashtali is going to eliminate players:

There is an unrooted tree with 𝑛n vertices. Every player has 22 special vertices 𝑥𝑖xi and 𝑦𝑖yi.

In one operation, Mashtali can choose any vertex 𝑣v of the tree. Then, for each remaining player 𝑖i he finds a vertex 𝑤w on the simple path from 𝑥𝑖xi to 𝑦𝑖yi, which is the closest to 𝑣v. If 𝑤𝑥𝑖w≠xi and 𝑤𝑦𝑖w≠yi, player 𝑖i 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?”

Since he was only thinking about the money, he couldn’t solve the problem by himself and asked for your help!

Input Squid Game solution codeforces

The first line contains 22 integer 𝑛n and 𝑚m (1𝑛,𝑚3105)(1≤n,m≤3⋅105) — the number of vertices of the tree and the number of players.

The second line contains 𝑛1n−1 integers 𝑝𝑎𝑟2,𝑝𝑎𝑟3,,𝑝𝑎𝑟𝑛par2,par3,…,parn (1𝑝𝑎𝑟𝑖<𝑖)(1≤pari<i) — denoting an edge between node 𝑖i and 𝑝𝑎𝑟𝑖pari.

The 𝑖i-th of the following 𝑚m lines contains two integers 𝑥𝑖xi and 𝑦𝑖yi (1𝑥𝑖,𝑦𝑖𝑛,𝑥𝑖𝑦𝑖)(1≤xi,yi≤n,xi≠yi) — the special vertices of the 𝑖i-th player.

Output

Print the minimum number of operations Mashtali has to perform.

If there is no way for Mashtali to eliminate all the players, print 1−1.

Examples
input

Copy
6 3
1 1 1 4 4
1 5
3 4
2 6

output Squid Game solution codeforces

2
input

Copy
5 3
1 1 3 3
1 2
1 4
1 5
output

Copy
-1

Note Squid Game solution codeforces

Explanation for the first sample:

In the first operation, Mashtali can choose vertex 11 and eliminate players with colors red and blue. In the second operation, he can choose vertex 66 and eliminate the player with orange color.
In the second sample, Mashtali can’t eliminate the first player.

 

Leave a Comment

Your email address will not be published. Required fields are marked *