Строка и перестановка

Вам дана строка $s\_1 s\_2 \ldots s\_n$, состоящая из $n$ маленьких английских букв. Жюри загадало перестановку $p\_1, p\_2, \ldots, p\_n$ и получило новую строку $t$, поставив $i$-й символ строки $s$ на $p\_i$-ю позицию в строке $t$. Вам необходимо найти строку $t$.

Для этого вы можете один раз задать вопрос, состоящий из $k$ выбранных вами пар индексов. Для пары индексов $(a\_i, b\_i)$ ($1 \leq i \leq k$, $1 \leq a\_i < b\_i \leq n$) вы узнаете, верно ли, что $p\_{a\_i} < p\_{b\_i}$.

Вы хотите определить искомую строку, спросив про наименьшее количество пар, то есть минимизируя значение числа $k$, при условии, что проверяющая программа является адаптивной. Это означает, что ответ к каждому тесту может быть различен в зависимости от того, про какие пары индексов вы спрашиваете. Другими словами, ваше решение должно успешно восстанавливать строку $t$ для любой возможной перестановки $p\_1, p\_2, \ldots, p\_n$.

В первом примере сделан запрос про пару индексов $(1, 2)$, в ответ получена строка <<1>>, что означает, что $p\_1 < p\_2$, и, следовательно, загадана перестановка $p =$<<$1$ $2$>>, то есть искомая строка --- <<ab>>.

Во втором примере сделан запрос про пару индексов $(1, 2)$, в ответ получена строка <<0>>, это означает, что $p\_1 \geq p\_2$, и, следовательно, загадана перестановка $p =$<<$2$ $1$>>, то есть искомая строка --- <<ba>>.

В третьем примере не спрашивается ни про какие пары индексов, а сразу выводится ответ --- строка <<qqq>>.

В четвертом примере была загадана перестановка <<$2$ $3$ $1$>>.