{"raw_statement":[{"iden":"statement","content":"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.\n\nDoctor Sufyan hates cheating, and this particular class of N students was known for cheating in almost every exam they took. \n\nHe 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. \n\nGiven 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.\n\nThe 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.\n\nThe 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.\n\nEach 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.\n\nIt is guaranteed that each pair of students will appear at most once.\n\nPrint the number of pairs of students that might be able to cheat.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"Print the number of pairs of students that might be able to cheat."},{"iden":"examples","content":"Input4 34 2 1 32 43 21 2Output1Input10 71 2 3 4 5 10 9 8 7 61 47 32 99 65 105 98 2Output3"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, M \\in \\mathbb{Z}^+ $ denote the number of students and the number of cheating pairs, respectively.  \nLet $ S = (s_1, s_2, \\dots, s_N) $ be the seating arrangement, where $ s_i \\in \\{1, 2, \\dots, N\\} $ is the student ID at position $ i $ (circular).  \nLet $ P = \\{(a_j, b_j) \\mid j \\in \\{1, \\dots, M\\}\\} $ be the set of cheating pairs, with $ a_j \\ne b_j $.\n\nDefine a position function $ \\text{pos}: \\{1, \\dots, N\\} \\to \\{1, \\dots, N\\} $ such that $ \\text{pos}(x) = i $ iff $ s_i = x $.\n\n**Constraints**  \n1. $ 3 \\le N \\le 10^4 $  \n2. $ 1 \\le M \\le \\binom{N}{2} $  \n3. All student IDs in $ S $ are distinct and in $ \\{1, \\dots, N\\} $  \n4. For each pair $ (a, b) \\in P $, $ a \\ne b $\n\n**Objective**  \nFor each pair $ (a, b) \\in P $, let $ i = \\text{pos}(a) $, $ j = \\text{pos}(b) $.  \nCompute the two circular distances:  \n- $ d_1 = |i - j| - 1 $  \n- $ d_2 = N - |i - j| - 1 $  \n\nThe pair $ (a, b) $ can cheat **if and only if** both $ d_1 $ and $ d_2 $ are even.  \nCount the number of such pairs in $ P $.","simple_statement":"You are given a round table with N seats and N students sitting around it. There are M pairs of friends. Two friends can cheat if the number of students between them is odd in both directions around the table. Count how many of these M pairs can cheat.","has_page_source":false}