### IOI '15 - Almaty, Kazakhstan

## Sorting

Aizhan has a sequence of `N` integers `S`[0], `S`[1], …, `S`[`N` − 1]. The sequence consists of distinct numbers from 0 to `N` − 1. She is trying to sort this sequence in ascending order by swapping some pairs of elements. Her friend Ermek is also going to swap some pairs of elements — not necessarily in a helpful way.

Ermek and Aizhan are going to modify the sequence in a series of rounds. In each round, first Ermek makes a swap and then Aizhan makes another swap. More precisely, the person making a swap chooses two valid indices and swaps the elements at those indices. Note that the two indices do not have to be distinct. If they are equal, the current person swaps an element with itself, which does not change the sequence.

Aizhan knows that Ermek does not actually care about sorting the sequence `S`. She also knows the exact indices Ermek is going to choose. Ermek plans to take part in `M` rounds of swapping. We number these rounds from 0 to `M` − 1. For each `i` between 0 and `M` − 1 inclusive, Ermek will choose the indices `X`[`i`] and `Y`[`i`] in round `i`.

Aizhan wants to sort the sequence `S`. Before each round, if Aizhan sees that the sequence is already sorted in ascending order, she will terminate the entire process. Given the original sequence `S` and the indices Ermek is going to choose, your task is to find a sequence of swaps, which Aizhan can use to sort the sequence `S`. In addition, in some subtasks you are required to find a sequence of swaps that is as short as possible. You may assume that it is possible to sort the sequence `S` in `M` or fewer rounds.

Note that if Aizhan sees that the sequence `S` is sorted after Ermek's swap, she can choose to swap two equal indices (e.g., 0 and 0). As a result the sequence `S` is also sorted after the entire round, so Aizhan reaches her goal. Also note that if the initial sequence `S` is already sorted, the minimal number of rounds needed to sort it is 0.

### Example 1

Suppose that:

- The initial sequence is
`S`= 4, 3, 2, 1, 0. - Ermek is willing to make
`M`= 6 swaps. - The sequence
`X`and`Y`that describe the indices Ermek is going to choose are`X`= 0, 1, 2, 3, 0, 1 and`Y`= 1, 2, 3, 4, 1, 2. In other words, the pairs of indices that Ermek plans to choose are (0, 1), (1, 2), (2, 3), (3, 4), (0, 1), and (1, 2).

In this setting Aizhan can sort the sequence `S` into the order 0, 1, 2, 3, 4 in three rounds. She can do so by choosing the indices (0, 4), (1, 3), and then (3, 4). The following table shows how Ermek and Aizhan modify the sequence.

Round | Player | Pair of swapped indices | Sequence |
---|---|---|---|

beginning | 4, 3, 2, 1, 0 | ||

0 | Ermek | (0, 1) | 3, 4, 2, 1, 0 |

0 | Aizhan | (0, 4) | 0, 4, 2, 1, 3 |

1 | Ermek | (1, 2) | 0, 2, 4, 1, 3 |

1 | Aizhan | (1, 3) | 0, 1, 4, 2, 3 |

2 | Ermek | (2, 3) | 0, 1, 2, 4, 3 |

2 | Aizhan | (3, 4) | 0, 1, 2, 3, 4 |

### Example 2

Suppose that:

- The initial sequence is
`S`= 3, 0, 4, 2, 1. - Ermek is willing to make
`M`= 5 swaps. - The pairs of indices that Ermek plans to choose are (1, 1), (4, 0), (2, 3), (1, 4), and (0, 4).

In this setting Aizhan can sort the sequence `S` in three rounds, for example by choosing the pairs of indices (1, 4), (4, 2), and then (2, 2). The following table shows how Ermek and Aizhan modify the sequence.

Round | Player | Pair of swapped indices | Sequence |
---|---|---|---|

beginning | 3, 0, 4, 2, 1 | ||

0 | Ermek | (1, 1) | 3, 0, 4, 2, 1 |

0 | Aizhan | (1, 4) | 3, 1, 4, 2, 0 |

1 | Ermek | (4, 0) | 0, 1, 4, 2, 3 |

1 | Aizhan | (4, 2) | 0, 1, 3, 2, 4 |

2 | Ermek | (2, 3) | 0, 1, 2, 3, 4 |

2 | Aizhan | (2, 2) | 0, 1, 2, 3, 4 |

Given the sequence `S`, the number `M`, and the sequence of indices `X` and `Y`, compute a sequence of swaps, which Aizhan can use to sort the sequence `S`. In subtasks 5 and 6 the sequence of swaps you find has to be the shortest possible.

You may assume that there exists a solution that requires `M` or fewer rounds.

### Input Format

Line 1 of input will contain the single integer `N`, representing the length of the sequence `S`.

Line 2 will contain an array of `N` space-separated integers `S`[0], …, `S`[`N` − 1] representing the initial sequence `S`.

Line 3 will contain the single integer `M` representing the number of swaps Ermek plans to make.

Lines 4, …, `M` + 3 will each contain a pair of space-separated integers `X`[`i`] and `Y`[`i`], respectively representing the length `M` arrays `X` and `Y`. For 0 ≤ `i` ≤ `M` − 1, in round `i` Ermek plans to swap numbers of indices `X`[`i`] and `Y`[`i`].

### Output Format

Use the input arrays to report one possible sequence of swaps Aizhan can make to sort the sequence `S`.

Line 1 of output should contain a single value `R` representing the length of the sequence of swaps that your program has found.

Line 2 + `i`, for 0 ≤ `i` < `R` should contain a pair of space-separated integers `P`[`i`] and `Q`[`i`], representing the indices Aizhan should choose in round `i`.

### Sample Input 1

5 4 3 2 1 0 6 0 1 1 2 2 3 3 4 0 1 1 2

### Sample Output 1

3 0 4 1 3 3 4

### Sample Input 2

5 3 0 4 2 1 5 1 1 4 0 2 3 1 4 0 4

### Sample Output 2

3 1 4 4 2 2 2

### Subtasks

subtask | points | N | M | extra contraints on X, Y | requirement on R |
---|---|---|---|---|---|

1 | 8% | 1 ≤ N ≤ 5 | M = N^{2} | X[i] = Y[i] = 0 for all i | R ≤ M |

2 | 12% | 1 ≤ N ≤ 100 | M = 30N | X[i] = Y[i] = 0 for all i | R ≤ M |

3 | 16% | 1 ≤ N ≤ 100 | M = 30N | X[i] = 0, Y[i] = 1 for all i | R ≤ M |

4 | 18% | 1 ≤ N ≤ 500 | M = 30N | none | R ≤ M |

5 | 20% | 6 ≤ N ≤ 2,000 | M = 3N | none | minimum possible |

6 | 26% | 6 ≤ N ≤ 200,000 | M = 3N | none | minimum possible |

All Submissions

Best Solutions

**Point Value:** 20 (partial)

**Time Limit:** 1.50s

**Memory Limit:** 2048M

**Added:** Sep 05, 2015

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

dev6on Sep 05, 2016 - 8:58:01 am UTC Why aren't new questions being posted?ImaxBlueon Sep 08, 2016 - 4:12:57 pm UTC Re: Why aren't new questions being posted?As to your second question, the ioi online format is not as suitable to other questions(which generally have offline-only solution), and the interactive judge is unable at this time. Also, some problems are much more suitable to the general majority of coders due to the offline solution being available(I.E. IOI 2013 game).

Edit: In progress

koosagaon Sep 09, 2015 - 12:01:13 am UTC Is judge correct in this problem?http://oj.uz/submission/16564

Please check the special judge.

jargonon Sep 12, 2015 - 8:46:25 pm UTC Re: Is judge correct in this problem?Alexon Sep 17, 2015 - 6:33:48 am UTC Re: Is judge correct in this problem?