Parcel Delivery Scheduling

There is a directed graph with \(N\) nodes and \(N\) edges. The nodes are numbered from \(1\) to \(N\). For each \(i\) (\(1 \le i \le N\)), there is an edge going from node \(i\) to node \(P_i\) and it takes exactly \(1\) unit time to traverse an edge. (Note that it is possible that \(i = P_i\).)

There are \(M\) parcels. For the \(j\)th parcel (\(1 \le j \le M\)), it must be transported from node \(A_j\) to node \(B_j\). All parcels start moving at time \(0\). A key constraint is that each edge can carry at most one parcel at any given time (i.e. each edge can be used by at most one parcel per unit time), whereas nodes can store an arbitrary number of parcels.

Your task is to determine if it is possible to deliver all the parcels to their destinations following the unique route prescribed by the graph (that is, a parcel starting at \(A\) will follow \(A, P_A, P_{P_A}, \ldots\) until it reaches \(B\)). Note that for a parcel, if \(B\) does not appear in the sequence generated by repeatedly applying \(P(\cdot)\), then it is impossible to deliver that parcel.

If it is possible to deliver every parcel, compute the minimum possible time such that all parcels have been delivered, under an optimal scheduling of the edge usages. Formally, if \(T_j\) is the arrival time of the \(j\)th parcel (which is the time when it first reaches node \(B_j\) in its route), you must minimize \(\max_{1\le j\le M} T_j\) while obeying the following conditions:

• For each parcel, its route is \(v_0, v_1, \dots, v_k\) with \(v_0 = A_j\) and \(v_k = B_j\);
• For each edge used, the transit takes exactly \(1\) unit time;
• At any time unit, an edge can be used by at most one parcel (if several parcels are waiting at a node to use its outgoing edge, they can be scheduled in any order, but no two may traverse the same edge simultaneously);
• A parcel may wait arbitrarily at a node.

If delivery for every parcel is possible, output the minimum possible value of \(\max_{j} T_j\). Otherwise, output \(-1\).

Note: If there is a formula it must be written in \(\LaTeX\) format (for example, \(\max_{1\le j\le M} T_j\)).

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of nodes/edges and the number of parcels).

The second line contains \(N\) integers: \(P_1, P_2, \dots, P_N\) where each \(P_i\) denotes that there is an edge from node \(i\) to node \(P_i\).

The following \(M\) lines each contain two integers \(A_j\) and \(B_j\) (the start and destination nodes for the \(j\)th parcel).

outputFormat

If it is possible to deliver all parcels, output a single integer representing the minimum possible time by which every parcel is delivered. Otherwise, output \(-1\).

sample

3 2
2 3 3
1 3
2 3

2