Давайте посмотрим на задачу как на графовую задачу. У нас есть вершины (солдаты), и ориентированный граф, где из вершины x идет ребро в y, если солдат под номером x выше солдата под номером y. Нам нужно упорядочить солдатов так, чтобы никакой солдат слева не был выше солдата справа, то есть чтобы для любого известного ребра (x, y) x шло раньше чем y. Все ребра в нашем построении должны идти направо. А так же заметим, что такое построение в целом возможно, только если в графе нет циклов.

Если в графе всё таки нет циклов, он представляет собой набор деревьев. В каждом дереве корень -- самый высокий солдат из всех, с которыми связан либо он либо связанные с ним солдаты. Если мы начнем обходить дерево dfs-ом из него, то в каждую вершину в дереве мы зайдем только после ее родителя (солдата выше), и получается что каждую вершину мы посетим после вершины, которая должна стоять раньше нее в ответе. Тогда для этого дерева нам достаточно взять вершины в ответ в порядке их обхода dfs-ом из корня. Такое упорядочивание вершин называется Топологическая сортировка. Так как деревья между собой не связаны ребрами, нам неважно в каком порядке относительно друг друга в ответе будут находиться вершины из разных деревьев, поэтому просто выпишем каждое дерево по порядку.

Итого:
1) Проверим граф на ацикличность, если циклы есть ответ "No". Про проверку графа на ацикличность можно почитать здесь http://e-maxx.ru/algo/finding_cycle
2) Найдем все корни -- это будут вершины, в которых не идет ни одно ребро
3) Запустим dfs из каждого корня, запишем в ответ вершины в порядке посещения

Пример кода на python:
def dfs(h):
    used[h] = 1
    answ.append(h + 1)
    for e in g[h]:
        if used[e] == 1:
            print('No') #пытаемся пойти в нашего родителя (вершину, из поддерева которой еще не вышли)
            exit(0)
        if used[e] == 0:
            dfs(e)
    used[h] = 2 #обошли всё поддерево, "закрываем" вершину


n, m = map(int, input().split())
g = [set([]) for i in range(n)] #set чтобы убрать повторы
is_root = [True] * n
for i in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    is_root[y] = False
    g[x].add(y)
used = [0] * n
answ = []
for i in range(n):
    if is_root[i]:
        dfs(i)
if False in used: #если кого-то не посетили, значит есть компонента, которая полностью цикл (у нее нет "корня")
    print('No')
else:
    print('Yes')
    print(*answ)