Island Ties Conquest

You are stranded on an island with several villages. Each village originally adores its own unique tie color. The island is connected by roads; two villages are considered neighbors if they are directly connected by a road.

Every week, exactly one persuasion event occurs: one village (say, village A) may convince one of its neighboring villages (say, village B) to change its tie color to A’s color. However, this persuasion event can only occur if the total number of islanders already supporting A’s tie color is not less than the number of islanders currently supporting B’s tie color. When B is convinced, its entire population joins A’s group, increasing the total count for that tie color. With time, through a sequence of such events (always obeying the rule that the conquering group’s size is at least as large as the target’s), the entire island ends up unified with a single tie color.

You must determine which initial tie colors could potentially dominate the island in some valid sequence of persuasion events. In other words, for each village (each originally having its own tie color), decide whether there exists an order of valid persuasion events (always merging an adjacent unconvinced village whose population does not exceed the total population of the current group) that would allow that village’s tie color to eventually spread to every village on the island. To be safe at the ferry, you plan to wear a tie of every color that might be the island’s final choice.

Note: The persuasion event across an edge is only allowed if the current total population of the persuading group (which may have merged several villages already) is greater than or equal to the population of the neighboring village being convinced. Once convinced, the neighboring village’s population is added to the persuading group.

You are given a description of the island: the number of villages, the roads between them, and the population of each village. All villages are numbered from 1 to n, and each village’s initial tie color is uniquely identified by its village number.

inputFormat

The input begins with two integers n and m (2 ≤ n, m ≤ 2000) representing the number of villages and the number of roads, respectively.

The second line contains n integers p₁, p₂, …, p_n (1 ≤ p_i ≤ 10⁹), where p_i is the population of village i.

The next m lines each contain two integers u and v (1 ≤ u, v ≤ n, u ≠ v) indicating that there is a road connecting villages u and v. It is guaranteed that the island is connected (i.e. there is a path between any two villages).

outputFormat

Output a list of village numbers in increasing order separated by a single space. Each number represents an initial tie color that can possibly become the final tie color of the island following some valid sequence of persuasion events.

sample

3 2
3 1 2
1 2
2 3

1 3