Do you know the company "Just Odd Inventions"? The business of this company is to create "just odd inventions." Here, we will call it JOI.

By the way, do you know the company "Incredibly Odd Inventions"? The business of this company is to create "incredibly odd inventions." Here, we will call it IOI.

Both JOI and IOI have $N$ employees each. The employees of JOI are named $j_1, j_2, \dots, j_N$, and the employees of IOI are named $i_1, i_2, \dots, i_N$. Also, one of the employees in JOI is the president of JOI, and one of the employees in IOI is the president of IOI. For every employee except the president, there is exactly one employee in the same company who is their direct superior.

Figure 1: Examples of the organizational structures of JOI and IOI. The arrows originating from the circles representing employees point to their direct subordinates.

IOI always creates "incredibly odd inventions" by stealing information from JOI's research projects. Now, $M$ research projects named $r_1, r_2, \dots, r_M$ have been launched at JOI, and $M$ spy projects named $s_1, s_2, \dots, s_M$ have been launched at IOI. IOI's spy project $s_b$ is a project to steal information from JOI's research project $r_b$.

The way employees are assigned to projects is the same for both JOI and IOI. For each project, one leader is assigned, and the leader gives orders to all of their direct subordinates. The employees who receive the orders then give the same orders to all of their own direct subordinates. All employees who receive the orders, along with the leader, belong to that project; other employees do not.

Figure 2: Examples of projects in JOI and IOI from Figure 1.

An IOI employee $i_a$ steals information from a JOI employee $j_a$. An IOI employee $i_a$ who belongs to spy project $s_b$ succeeds in their espionage activity if the JOI employee $j_a$ belongs to research project $r_b$. Every employee in each company may belong to multiple projects, and an IOI employee may succeed in espionage activities in multiple spy projects.

Task

Given the information about the employees and projects in JOI and IOI, write a program that calculates, for each IOI employee, how many spy projects they succeed in their espionage activities.

Input

Read the following from standard input:

• The first line contains two integers $N$ and $M$, separated by a space, representing that JOI and IOI each have $N$ employees, and there are $M$ research projects and $M$ spy projects.
• Of the following $N$ lines, the $a$-th line ($1 \le a \le N$) contains two integers $P_a$ and $Q_a$ ($0 \le P_a \le N$ and $0 \le Q_a \le N$), representing that JOI employee $j_a$ is a direct subordinate of employee $j_{P_a}$, and IOI employee $i_a$ is a direct subordinate of employee $i_{Q_a}$. If $P_a = 0$, employee $j_a$ is the president of JOI, and if $Q_a = 0$, employee $i_a$ is the president of IOI.
• Of the following $M$ lines, the $b$-th line ($1 \le b \le M$) contains two integers $R_b$ and $S_b$ ($1 \le R_b \le N$ and $1 \le S_b \le N$), representing that the leader of research project $r_b$ is employee $j_{R_b}$, and the leader of spy project $s_b$ is employee $i_{S_b}$.

Output

Output $N$ lines to standard output. The $a$-th line ($1 \le a \le N$) should contain a single integer representing how many spy projects IOI employee $i_a$ succeeds in their espionage activities.

Constraints

All input data satisfies the following conditions:

• $1 \le N \le 2\,000$.
• $1 \le M \le 500\,000$.

Subtasks

Subtask 1 [10 points]

• $N \le 200$.
• $M \le 200$.

Subtask 2 [20 points]

• $M \le 2\,000$.

Subtask 3 [70 points]

• No additional constraints.

Examples

Input 1

3 4
0 2
1 0
2 2
1 1
2 1
2 3
3 2

Output 1

1
0
2

Note

This input/output corresponds to the example in the problem description. In this case:

• Employee $i_1$, who belongs to spy projects $s_1, s_2, s_4$, succeeds in espionage activity in spy project $s_1$ because employee $j_1$ belongs to research project $r_1$.
• Employee $i_2$, who belongs to spy project $s_4$, does not succeed in any spy project because employee $j_2$ does not belong to research project $r_4$.
• Employee $i_3$, who belongs to spy projects $s_3, s_4$, succeeds in espionage activities in spy projects $s_3, s_4$ because employee $j_3$ belongs to research projects $r_3, r_4$.