Hiking Gwanaksan

Seoul National University has a well known line: "If anyone asks about the future of our country, tell them to raise their head and look at Gwanak." One day Unused asked Corea about the future of the country, and Corea decided to climb Gwanaksan, see that future in person, and report back.

The trail network of Gwanaksan consists of $N$ rest areas numbered 1 through N and $M$ roads, each of which lets a hiker move between two rest areas. Corea finds it far too much trouble to climb from ground level, so he takes the cable car, gets off at any rest area he likes, and starts hiking from there. Corea always aims higher, so at each rest area he picks one road that leads to a directly connected rest area of greater height and follows it. If no such road exists, he finishes the hike.

Every rest area on Gwanaksan has one observation deck from which the future of the country is visible. Corea wants to visit as many rest areas as possible so that he can report plenty of that future to Unused. Given the map of Gwanaksan, find the largest number of rest areas Corea can visit when he starts from each rest area. The rest area where he leaves the cable car counts as a visited rest area.

The first line contains the number of rest areas on the trail network, $N$ ($2 \le N \le 5000$), and the number of roads connecting two rest areas, $M$ ($1 \le M \le 100000$).

The second line contains $N$ integers giving the height of each rest area in order of rest area number. Each height is an integer between $1$ and $1000000$, and all heights are different.

Each of the next $M$ lines contains the numbers of the two rest areas that one road connects, separated by a space. A rest area number is an integer between $1$ and $N$. No road has the same rest area at both ends, and several roads may connect the same pair of rest areas.

Print $N$ lines. On the $n$-th line, print the largest number of rest areas Corea can visit when he starts hiking from rest area $n$.

The picture above is the map of the first example. Starting from rest area 2, visiting rest areas 1, 4 and 3 in that order reaches the largest number of rest areas.

Rest area 5 is higher than rest area 3, but no road joins the two, so Corea cannot move from rest area 3 to rest area 5.