- Time limit: 1.00 s
- Memory limit: 512 MB
There are cities in Byteland numbered from to . It is well known that in the th city, ice cream of flavor is sold. There are bidirectional roads connecting the cities. Citizens of a city have access to an ice cream flavor if they can travel trough some roads (possibly none) to a city where the flavor is sold. For each city compute how many distinct flavors of ice cream the citizens have access to.
Input
The first line of input contains two integers, and . Next line contains integers, . The flavor of ice cream for each city. Next lines each contain two integers, and indicating that there is a road between cities and .
Output
Output one line containing integers, the number of flavors each city has access to.
Constraints
Example
Input:
5 4 1 6 1 5 4 2 4 1 3 2 5 5 4
Output:
1 3 1 3 3