404044: GYM101401 H Data Structures Exam (A)

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Data Structures Exam (A)time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

It's exam week at PSUT, and Doctor Sufyan is in big trouble; the room he had reserved for his Data Structures exam was preoccupied and the only available room left was the meeting room, which had a single large round table with N seats around it numbered from 1 to N in one direction.

Doctor Sufyan hates cheating, and this particular class of N students was known for cheating in almost every exam they took.

He knows that there are M pairs of friends in this class that are likely to copy each other's answers. However, the two friends will not be able to cheat if there is an even number of students seated between them from both directions.

Given the number of students in this class N, their seating order around the table, and the potential cheating pairs of friends, help Doctor Sufyan figure out the number of pairs that might be able to cheat.

Input

The first line of input contains two space-separated integers N, M (3 ≤ N ≤ 104) , the number of students (and seats) and the number of cheating pairs of friends, respectively.

The second line contains N distinct space-separated integers between 1 and N, representing the seating order of the students around the table; the ith integer represents the ID (from 1 to N) of the student sitting in the ith position.

Each of the following M lines contains two space-separated integers a b (1 ≤ a, b ≤ N) (a ≠ b), represent a pair of friends that are most likely to cheat.

It is guaranteed that each pair of students will appear at most once.

Output

Print the number of pairs of students that might be able to cheat.

ExamplesInput
4 3
4 2 1 3
2 4
3 2
1 2
Output
1
Input
10 7
1 2 3 4 5 10 9 8 7 6
1 4
7 3
2 9
9 6
5 10
5 9
8 2
Output
3

加入题单

上一题 下一题 算法标签: