You are given a rooted tree with ~N~ nodes. There are ~M~ trips, the ~i~-th starting at ~A_i~ and ending at ~B_i~. The distance of a trip is the number of edges on the unique path between the endpoints.

For each node ~v~, you may perform the following operation:

• Remove the edge from ~v~ to its parent ~p(v)~. Add an edge from ~p(v)~ to any node in the subtree rooted at ~v~ (could be ~v~ itself).

For each node ~v~, what is the minimum sum of trip distances you can get after performing this operation once on ~v~? If ~v~ is the root, output the original sum.

Input

The first line contains two integers ~N~ and ~M~ (~1 \le N, M \le 2 \times 10^5~) — the number of nodes in the tree and the number of trips.

The second line contains ~N-1~ integers ~p_2, p_3, \ldots, p_N~, where ~p_i~ (~1 \le p_i < i~) is the parent of node ~i~. Node ~1~ is the root of the tree.

The next ~M~ lines each contain two integers ~A_i~ and ~B_i~ (~1 \le A_i, B_i \le N~), representing the start and end points of the ~i~-th trip.

Output

Output ~N~ lines. The ~v~-th line should contain the minimum possible sum of trip distances after performing the operation on node ~v~. If node ~v~ is the root, output the original sum of trip distances.

Examples

Input 1

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

Output 1

6
4
6
4
6

Explanation 1

The tree structure is:

    1
   /
  2
 / \
3   4
     \
      5

The original trip distances are

• Trip 1→5 has a distance of 3 (1→2→4→5)
• Trip 2→3 has a distance of 1 (2→3)
• Trip 2→5 has a distance of 2 (2→4→5)

so the total distance is 6.

For node 1 (the root), we just output the original distance of 6.

For node 2, we can remove the edge 1→2 and reconnect 1 to any node in the subtree of 2 (either 2, 3, 4 or 5). If we reconnect 1→5

• Trip 1→5 will have a distance of 1 (1→5)
• Trip 2→3 will have a distance of 1 (2→3)
• Trip 2→5 will have a distance of 2 (2→4→5)

so the total distance will be 4. This can be shown to be the minimum possible.

For node 3, after removing the edge 2→3 we must reconnect it so we output the original distance of 6.

For node 4, we can remove the edge 2→4 and reconnect 2 to any node in the subtree of 4 (either 4 or 5). If we reconnect 2→5

• Trip 1→5 will have a distance of 2 (1→2→5)
• Trip 2→3 will have a distance of 1 (2→3)
• Trip 2→5 will have a distance of 1 (2→5)

so the total distance will be 4. This can be shown to be the minimum possible.

For node 5, after removing the edge 4→5 we must reconnect it so we output the original distance of 6.

Input 2

4 2
1 1 2
1 4
3 2

Output 2

4
4
4
4

Explanation 2

The tree structure is:

    1
   / \
  2   3
   \
    4

The original trip distances are

• Trip 1→4 has a distance of 2 (1→2→4)
• Trip 3→2 has a distance of 2 (3→1→2)

so the total distance is 4.

No matter what node we try to perform this operation on, the total distance must be 4.

Of note, if we remove the edge 1→2 and add the edge 1→4

• Trip 1→4 will have a distance of 1 (1→4)
• Trip 3→2 will have a distance of 3 (3→1→4→2)

so the total distance will still be 4.

Input 3

10 6
1 1 2 2 3 3 4 4 5
1 10
1 10
1 10
3 8
3 7
7 8

Output 3

19
17
19
17
16
19
19
19
19
19