各選手について，その隣にいる人が確定しているかどうか，また確定していればその選手の番号を持っておきます．
すると，順位変動においては高々 $4$ 人の情報しか変わりません．したがって，最終的な各選手の両隣に関する情報は $O(M)$ で計算できます．

次に，両隣の情報から列を復元する方法です．まず，列の端としてありうるのは隣にいることが確定している人が $2$ 人未満の選手です．
したがって，$i = 1, 2, \cdots, N$ の順にその選手が列の端としてありうるかを判定し，ありうるならば選手 $i$ から両隣の情報を用いて列の残りの人を求めれば良いです．

既に誰を見たかの情報を管理しておけば，この探索において列挙される列について，先頭は単調増加 ($i$ の探索順より明らか) であり，先頭は末尾以下 (もしそうでないなら，末尾の選手について判定したときにその列は列挙されている) となります．
よって列の sort などは不要となり，列の列挙に関しては $O(N)$ となります．

したがって，\(O(N + M)\) でこの問題は解けます．