There are n cities in Byteland numbered from 1 to n. It is well known that in the ith city, ice cream of flavor a_i is sold. There are m 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, n and m. Next line contains n integers, a_1, \ldots, a_n. The flavor of ice cream for each city. Next m lines each contain two integers, u_i and v_i indicating that there is a road between cities u_i and v_i.

Output

Output one line containing n integers, the number of flavors each city has access to.

Constraints

• 1 \le n \le 10^5
• 1 \le a_i \le 10^5
• 1 \le m \le 10^5
• 1 \le u_i, v_i \le n

Example

Input:

5 4
1 6 1 5 4
2 4
1 3
2 5
5 4

Output:

1 3 1 3 3