Nils is a celebrity, and the paparazzi are obsessed with taking photos of him!
There are towns labelled from to , with bidirectional roads between them such that it is possible to travel from any town to any other town only using those roads. The -th road connects towns and . Initially, there is one paparazzo in each town, hoping to get a glimpse of Nils.
Nils will then make appearances. On the -th appearance, he will appear in town . Then, each paparazzo will move one town towards Nils. Formally, each paparazzo with move to the unique adjacent town which is closer to than their current town, where distance is defined as the minimum number of roads needed to be travelled to reach one town from another. The exception to this rule is that paparazzi which are already in town will not move.
Note that Nils, being a celebrity, has access to a private jet, and is therefore not bound by the roads. This means that consecutive appearances are not necessarily in adjacent towns. Furthermore, consecutive appearances may be in the same town.
After each appearance, can you determine the number of towns containing at least one paparazzo?
Any town can be reached from any other town by only travelling along the roads.
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
The first line contains two space-separated integers, and .
The -th of the following lines contains two space-separated integers, and .
The -th of the following lines contains a single integer, .
Output lines. The -th line should contain a single integer denoting the number of towns containing at least one paparazzo after the first appearances.
4 2 1 2 2 3 2 4 1 2
After the first appearance in town , there are paparazzi in towns and only.
After the second appearance in town , all paparazzi are in town .