Fleet Swap Optimization

The federation has \(N\) planets and a new administrative structure that forms a binary tree. The capital is the administrative center, and every other planet is divided into at most two regions recursively. Initially, every planet \(i\) has a space fleet with fighting power \(F_i\). In the administrative reform, the military regulations demand that in every administrative region the fleet stationed at the region’s center (i.e. the node in the binary tree) must be the strongest (i.e. have the maximum fighting power in that region).

To achieve this, the only allowed operation is to swap the fleets stationed on two planets. However, a swap can only be performed between two planets that are directly connected by an interstellar route. There are \(M\) bidirectional interstellar routes provided. In other words, you may swap the fleets on two planets if and only if there is a route between them.

The administrative structure is fixed: assume that the planets are arranged in a binary tree with planet \(1\) as the capital, and for every planet \(i\) its children (if they exist) are at indices \(2i\) and \(2i+1\) (taking only indices \(\le N\)). To satisfy the military regulation, the fleet deployed at a node must have the greatest fighting power among all fleets in its subtree.

Since the council wants to minimize the overall number of swaps, your task is to compute the minimum number of swaps required to rearrange the fleets so that for every node \(i\) (with children) the fighting power at node \(i\) is no less than that at any node in its subtree.

Hint: One valid final assignment is to assign the sorted fleet values in descending order in level‐order (i.e. node \(1\) gets the highest value, node \(2\) the second highest, etc.). It is easy to verify that this assignment satisfies the max–heap property (i.e. the required condition), and if the underlying interstellar network is connected (or at least allows swapping any two fleets via intermediate swaps), then any permutation is reachable. In this problem, you may assume that the given network allows the necessary swaps.

Note that the swap operation we consider swaps the fleets on the two planets directly (and counts as one swap); you do not need to output the actual sequence of swaps.

Task: Given \(N\), \(M\), the initial fleet fighting powers \(F_1, F_2, \dots, F_N\), and the \(M\) interstellar routes (which you may ignore in the calculation under the assumption that the network allows any needed swap), compute the minimum number of swaps needed so that if the fleets are rearranged according to the rules, the fleet at every node is the maximum in its subtree.

inputFormat

The first line contains two integers \(N\) and \(M\) (\(1 \le N \le 10^5\), \(0 \le M \le 10^5\)).

The second line contains \(N\) integers \(F_1, F_2, \dots, F_N\) representing the fighting power of the fleet on each planet. It is guaranteed that all \(F_i\) are distinct.

The next \(M\) lines each contain two integers \(u\) and \(v\) (\(1 \le u, v \le N\)) indicating that there is a bidirectional interstellar route between planets \(u\) and \(v\). You may assume that the network permits the necessary swaps.

outputFormat

Output a single integer, the minimum number of swaps required to rearrange the fleets so that in the final configuration (which obeys the max–heap property on the given binary tree structure) every administrative region has its center with the greatest fighting power in that region.

sample

3 3
3 1 2
1 2
2 3
1 3

1