# 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≤𝑛,𝑚≤3⋅105)(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.

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.

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

### output Squid Game solution codeforces

2

5 3 1 1 3 3 1 2 1 4 1 5

-1

#### Note Squid Game solution codeforces

Explanation for the first sample: