TAP2016C - Correlations

no tags 

[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2016 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2016/09/tap2016.pdf ]

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 \emph{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.

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 ( N,M ≤ 5 × 104). 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 ( 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 P1, P2, ..., PN, representing the subjects in the order Gabina will pass them ( Pi  N for i = 1, ..., N, with Pi ≠ Pj 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

hide comments
lonjinus: 2017-01-08 22:27:07

How i read the testcases in java, i try using that:
ava.io.BufferedReader entry = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
String s = entry.readLine();
while(s != null && s.length() != 0){}

:D: 2016-11-03 01:59:25

Yes, first four lines form a single test case. It's clear from input specification. You should read test cases until EOF.

vengatesh15: 2016-10-22 09:02:27

You haven't specified that How many test case will be there in one input file ?

vengatesh15: 2016-10-22 07:51:10

3 2
1 2
2 3
1 2 3
is this single test case?

Last edit: 2016-10-22 07:53:25

Added by:Fidel Schaposnik
Date:2016-09-21
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Argentinian Programming Tournament 2016