String and Permutation

Time limit1sMemory limit1024 MB

Summary

Given a string s and a hidden permutation p, find t where t[p_i] = s_i, using one batch of index-pair comparisons with as few pairs as possible.

Level: Medium6 of 10
Topics: String, Greedy, Implementation
Solved: No attempts yet

Problem

You are given a string s_1 s_2 ... s_n of n lowercase English letters. The jury chose a permutation p_1, p_2, ..., p_n and built a new string t by placing the i-th character of s at position p_i of t. Find the string t.

To do this, you can ask one question consisting of k pairs of indices. For a pair (a_i, b_i) (1 ≤ i ≤ k, 1 ≤ a_i < b_i ≤ n), you learn whether p_{a_i} < p_{b_i} holds.

Minimize k, the number of pairs in your question. The checker is adaptive: its answers may depend on which pairs you ask about. So your solution must recover t for every possible permutation p.

Hint

In the first example, the query is the pair (1, 2) and the answer is 1, which means p_1 < p_2. So the permutation is p = 1 2 and the string is ab.

In the second example, the query is the pair (1, 2) and the answer is 0, which means p_1 >= p_2. So the permutation is p = 2 1 and the string is ba.

In the third example, no pairs are asked and the answer qqq is printed directly.

In the fourth example, the hidden permutation is 2 3 1.

Examples4

Example 1
Input
```
ab


1
```
Expected output
```
1
1 2

ab
```
Example 2
Input
```
ab


0
```
Expected output
```
1
1 2

ba
```
Example 3
Input
```
qqq
```
Expected output
```
0

qqq
```
Example 4
Input
```
baa



10
```
Expected output
```
2
1 2
1 3

aba
```