{
    \parindent=1cm
    \begin{tabular}{l@{\extracolsep{1cm}}l}
         Идея: & Артем Васильев\\
         Разработка: & Геннадий Короткевич\\
     \end{tabular}
}

Найдём $k$~--- число рёбер, удовлетворяющих условию $u_i < v_i$. Если $k \ge \lceil \frac{m}{2} \rceil$, выведем перестановку $1, 2, \ldots, n$. В противном случае, выведем перестановку $n, n-1, \ldots, 1$.

Поскольку каждое ребро удовлетворяет либо условию $u_i < v_i$, либо условию $u_i > v_i$, в сумме перестановки $1, 2, \ldots, n$ и $n, n-1, \ldots, 1$ имеют ровно $m$ подходящих рёбер. А значит, хотя бы одна из них будет иметь хотя бы половину от $m$.

Так как это верно для любой пары перестановок $p_1, p_2, \ldots, p_n$ и $p_n, p_{n-1}, \ldots, p_1$, в качестве альтернативного решения можно генерировать случайные перестановки, пока не найдём ту, которая сработает. В среднем понадобится не более $2$ итераций.