Finishing your studies in a university is not only a matter of studying and learning. To obtain that prized degree, each student has to prove that he has learned, and in order to do that he needs to pass N subjects. However, it is often also necessary to abide by uncountable and deliberately complicated regulatory labyrinths.

At the Institute With Few Correlations (IWFC) there are antiquated norms which forbid students from passing some subjects without having first passed certain other subjects. The latter are called "correlation" subjects for the first ones. Each subject may have one or more correlation subjects, but there are no cyclic correlations, so that it is always possible to obtain the desired degree.

Gabina is a student of Happiness Sciences, and fortunately her professors are very understanding people. They therefore allow her to pass her subjects without actually having passed their correlation subjects before. The problem with this is that IWFC's electronic system can only register a subject as being passed abiding by the correlation rules. Thus, a subject will be registered in the system if and only if it was passed and all its correlation subjects are also already registered.

Seeing her progress keeps Gabina motivated, and helps her to push forward with her studies. For this reason, each time she passes a subject she checks the electronic system to see how many subjects have been registered in it. Sometimes she sees the number has not changed, which happens whenever the subject she just passed didn't have all its correlation subjects registered in the system. In other cases, she receives the delightful news that the number of registered subjects has increased. Moreover, it may happen that this increase was in more than one, which happens whenever the subject she just passed could be registered, and doing so unlocked the registration of a series of subjects passed beforehand.

Gabina has already planned the order in which she will pass all the subjects for her degree. She would now like to know the number of subjects which will be registered in the electronic system after she passes each one of them. Your task is to write a program to help Gabina predict this, so that she can joyfully finish her Happiness Sciences studies.

Input

There are multiple test cases in the input file. The first line contains two integer numbers N and M, representing the number of subjects in her degree and the number of correlation relations between pairs of subjects, respectively (1 ≤ N,M ≤ 5 × 10⁴). The subjects are numbered from 1 to N. Each of the following M lines contains two integer numbers A and B, indicating that subject A is a correlation subject for subject B (1 ≤ A, B ≤ N with A ≠ B). This means that subject A must be registered in the electronic system before subject B can be registered. There are no repeated or cyclic correlation relations in the input. The last line contains N integer numbers P₁, P₂, ..., P_N, representing the subjects in the order Gabina will pass them (1 ≤ P_i ≤ N for i = 1, ..., N, with P_i ≠ P_j for i ≠ j).

Output

For each test case, print N lines, each with a single integer number. The number printed in the i-th line represents the number of subjects registered in the electronic system immediately after Gabina passes the i-th subject for her degree in the order giver in the input.

Example

Input:
3 2
1 2
2 3
1 2 3
3 2
1 2
2 3
3 2 1
4 4
1 2
2 3
4 3
1 4
2 3 1 4

Output:
1
2
3
0
0
3
0
0
2
4