|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|8 초||128 MB||137||72||44||47.826%|
The JOI Co., Ltd. has N servers in total around the world. Each server contains an important piece of information. Different servers contain different pieces of information. The JOI Co., Ltd. is now building digital lines between the servers so that the pieces of information will be shared with the servers. When a line is built between two servers, pieces of information can be exchanged between them. It is possible to exchange pieces of information from one server to another server which is reachable through the lines which are already built.
Each server has a high-performance synchronization system. When two servers can exchange pieces of information each other and they contain different pieces of information, they automatically synchronize the pieces of information. After a synchronization between the server A and the server B, both of the servers A and B will contain all the pieces of information which are contained in at least one of the servers A and B before the synchronization.
In order to reduce the cost, only N − 1 lines can be built. After the N − 1 lines are built, there will be a unique route to exchange pieces of information from one server to another server without passing through the same server more than once.
In the beginning (at time 0), no lines are built. Sometimes, lines are built in a harsh condition (e.g. in a desert, in the bottom of sea). Some of the lines become unavailable at some point. Once a line becomes unavailable, it is not possible to use it until it is rebuilt.
It is known that, at time j (1 ≤ j ≤ M), the state of exactly one line is changed.
We need to know the number of different pieces of information contained in some of the servers at time M + 1.
Write a program which, given information of the lines to be built and the state of the lines, determine the number of different pieces of information contained in some of the servers
Read the following data from the standard input.
Write Q lines to the standard output. The k-th line (1 ≤ k ≤ Q) should contain an integer, the number of different pieces of information contained in the server Ck in the end.
Q = 1 is satisfied.
Xi = i, Yi = i + 1 (1 ≤ i ≤ N − 1) are satisfied.
There are no additional constraints.
5 6 3 1 2 1 3 2 4 2 5 1 2 1 4 4 3 1 4 5
3 5 4
In the beginning, we assume the server i (1 ≤ i ≤ 5) contains the piece i of information.
As explained above, in the end, the servers 1, 4, 5 have 3, 5, 4 different pieces of information, respectively.