CSES - KILO 2016 3/5 - Ice cream
  • Time limit: 1.00 s
  • Memory limit: 512 MB

There are nn cities in Byteland numbered from 11 to nn. It is well known that in the iith city, ice cream of flavor aia_i is sold. There are mm 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, nn and mm. Next line contains nn integers, a1,,ana_1, \ldots, a_n. The flavor of ice cream for each city. Next mm lines each contain two integers, uiu_i and viv_i indicating that there is a road between cities uiu_i and viv_i.

Output

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

Constraints

  • 1n1051 \le n \le 10^5
  • 1ai1051 \le a_i \le 10^5
  • 1m1051 \le m \le 10^5
  • 1ui,vin1 \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