73 lines
1.5 KiB
Java
73 lines
1.5 KiB
Java
package chelper;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.HashSet;
|
|
import java.util.List;
|
|
import java.util.Set;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import solutions.ChelperSolution;
|
|
|
|
|
|
public class TaskD extends ChelperSolution {
|
|
|
|
public static final long MAGIC = 1000000L;
|
|
|
|
@Override
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
super.solve(testNumber, in, out);
|
|
}
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
int n = in.nextInt();
|
|
int m = in.nextInt();
|
|
|
|
int[] positions = in.nextIntArray(n);
|
|
int[][] swaps = in.nextIntIntArray(m, 2);
|
|
|
|
int[] positionOf = new int[n + 1];
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
positionOf[positions[i]] = i;
|
|
}
|
|
|
|
Set<Long> set = new HashSet<>();
|
|
|
|
for (int i = 0; i < m; i++) {
|
|
int l = positionOf[swaps[i][0]];
|
|
int r = positionOf[swaps[i][1]];
|
|
|
|
set.add(l * MAGIC + r);
|
|
}
|
|
|
|
int nastya = n - 1;
|
|
|
|
List<Integer> jumpers = new ArrayList<>();
|
|
List<Integer> leftovers = new ArrayList<>();
|
|
// Set<Integer> jumpers = new HashSet<>();
|
|
// Set<Integer> leftovers = new HashSet<>();
|
|
leftovers.add(nastya);
|
|
|
|
for (int i = nastya - 1; i >= 0; i--) {
|
|
boolean ok = true;
|
|
|
|
for (Integer j : leftovers) {
|
|
if (!set.contains(i * MAGIC + j)) {
|
|
ok = false;
|
|
break;
|
|
}
|
|
}
|
|
|
|
if (ok) {
|
|
jumpers.add(i);
|
|
} else {
|
|
leftovers.add(i);
|
|
}
|
|
}
|
|
|
|
out.println(jumpers.size());
|
|
}
|
|
}
|