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

문제

Вам дана строка $s_1{s}_2\dots s_{n}s\_1\; s\_2\; \backslash ldots\; s\_n$, состоящая из $nn$ маленьких английских букв. Жюри загадало перестановку $p_1,p_2,\dots ,p_{n}p\_1,\; p\_2,\; \backslash ldots,\; p\_n$ и получило новую строку $tt$, поставив $ii$-й символ строки $ss$ на $p_{i}p\_i$-ю позицию в строке $tt$. Вам необходимо найти строку $tt$.

Для этого вы можете один раз задать вопрос, состоящий из $kk$ выбранных вами пар индексов. Для пары индексов $(a_i,b_i)(a\_i,\; b\_i)$ ($1\le i\le k1\; \backslash leq\; i\; \backslash leq\; k$, ) вы узнаете, верно ли, что .

Вы хотите определить искомую строку, спросив про наименьшее количество пар, то есть минимизируя значение числа $kk$, при условии, что проверяющая программа является адаптивной. Это означает, что ответ к каждому тесту может быть различен в зависимости от того, про какие пары индексов вы спрашиваете. Другими словами, ваше решение должно успешно восстанавливать строку $tt$ для любой возможной перестановки $p_1,p_2,\dots ,p_{n}p\_1,\; p\_2,\; \backslash ldots,\; p\_n$.

힌트

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

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

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

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