Arrange Participants with Adjacent Buddies

You are given a list of participant IDs and a list of pairs of buddies. Each buddy pair indicates that the two participants must be seated adjacent to each other in the final arrangement. You are allowed to swap only adjacent participants, but note that using a series of adjacent swaps any permutation can be achieved. In this problem, a simple strategy is adopted: sort the array of participant IDs using adjacent swaps (i.e. bubble sort) and then check whether each buddy pair appears as neighbors in the sorted order.

Mathematically, if \( P = [p_1, p_2, \dots, p_n] \) is the sorted array and for each buddy pair \( (a,b) \), we require that there exists an index \( i \) such that \( p_i = a \) and \( p_{i+1} = b \) (or vice versa). If this condition is satisfied for all buddy pairs, output True, otherwise output False.

inputFormat

The input is read from standard input (stdin) in the following format:

 n
 p1 p2 ... pn
 k
 a1 b1
 a2 b2
 ...
 ak bk

where:

• n is the number of participants.
• p1, p2, ..., pn are the participant IDs, separated by spaces.
• k is the number of buddy pairs.
• Each of the next k lines contains two integers a and b indicating that participant a and participant b must be seated adjacent.

outputFormat

The output is printed to standard output (stdout) as a single line: either True or False indicating whether it is possible to arrange the participants (via adjacent swaps) such that each buddy pair appears adjacent.

4
1 3 2 4
2
1 2
3 4

True