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!

mm 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: Squid Game solution codeforces

There is an unrooted tree with nn vertices. Every player has 22 special vertices xixi and yiyi.

In one operation, Mashtali can choose any vertex vv of the tree. Then, for each remaining player ii he finds a vertex ww on the simple path from xixi to yiyi, which is the closest to vv. If wxiw≠xi and wyiw≠yi, player ii 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!

Input

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

The second line contains n1n−1 integers par2,par3,,parnpar2,par3,…,parn (1pari<i)(1≤pari<i) — denoting an edge between node ii and paripari.

The ii-th of the following mm lines contains two integers xixi and yiyi (1xi,yin,xiyi)(1≤xi,yi≤n,xi≠yi) — the special vertices of the ii-th player.

Output Squid Game solution codeforces

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

Copy
2

input Squid Game solution codeforces

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