Galactic Race Strategy

The 10-year galactic race is about to begin! This prestigious competition takes place on a race course formed by \(N\) planets connected by \(M\) bidirectional interstellar routes. Each planet has a unique gravitational value. The rules require racers to start from a celestial body that is not connected to any of these \(N\) planets and then visit every planet exactly once. The first to complete this journey wins the race.

The high‐tech racing car, named Super Energy E-Donkey, can travel in two modes:

• High‐speed navigation mode: In this mode, the car uses an antimatter engine to blaze along interstellar routes at several times the speed of light. However, due to damage, it can only travel from a planet to another if the destination has a strictly higher gravitational value than the current planet. (That is, if you are at planet \(u\) with gravitational value \(g_u\) and you want to go to planet \(v\) with \(g_v\), you must have \(g_u < g_v\) and there must be an interstellar route connecting them.)
• Ability explosion mode: In this mode, the car breaks free from space–time constraints and can instantly jump to any planet after a fixed positioning delay.

Since the starting celestial body is not connected to any planet, the first move must use the ability explosion mode. For subsequent moves, if a valid high–speed route exists (i.e. a direct route from the current planet to the next with increasing gravitational values) then it takes negligible time; otherwise the car has to use the ability explosion mode with a fixed time penalty. Let each use of ability explosion mode count as 1 time unit. Thus, if you plan a route that visits the \(N\) planets in some order and achieve \(X\) valid high-speed transitions, the total time cost is:

[ \text{Time} = 1 + (N - 1 - X). ]

Your task is to help design a plan such that the total time is minimized. Note that the maximum number of valid transitions in any route is \(L - 1\), where \(L\) is the length of the longest path in the directed acyclic graph defined below. In this graph, every interstellar route connecting planets \(u\) and \(v\) becomes a directed edge from \(u\) to \(v\) if \(g_u < g_v\), or from \(v\) to \(u\) otherwise. Therefore, the optimal total time is given by:

[ \text{MinTime} = N - L + 1. ]

Determine the minimum time required to complete the race.

inputFormat

The input begins with a line containing two integers \(N\) and \(M\) representing the number of planets and the number of interstellar routes respectively.

The next line contains \(N\) distinct integers \(g_1, g_2, \ldots, g_N\) representing the gravitational values of the planets.

Each of the following \(M\) lines contains two integers \(u\) and \(v\), indicating that there is an undirected interstellar route connecting planet \(u\) and planet \(v\) (1-indexed).

outputFormat

Output a single integer representing the minimum time (in time units) required for the racer to complete the journey.

Note: The time cost is defined as 1 for each use of ability explosion mode. Since the first move always requires an explosion jump, if a route has \(X\) valid high-speed transitions then the total time cost is \(1 + (N-1 - X)\). Equivalently, if the longest chain (path) in the directed graph has length \(L\), the answer is \(N - L + 1\).

sample

1 0
100

1

</p>