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

Вам дана строка $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$>>.