Just Half is Enough

• 해결 방법은 다양하게 있지만, 발상만 잘 하면 굉장히 단순하게 풀 수 있는 방법이 있다.
• 방향 그래프를 2개의 비순환 그래프로 분할하는 방법에서 사용했던 것과 같은 아이디어로, 모든 u→v 에지는, u>v 인것 또는 u<v 인것의 두가지로 분류될수 있다는 것을 생각하면 된다. 만약, 1,2,3,..,n 으로 오더를 주게 되면 u<v 인 에지는 모두 조건을 만족하게 된다. 그러므로 u<v인 에지가 절반 이상이라면 이것으로 해결된다. 절반 미만이라면, n,n-1,…,1 로 오더를 주어서 u>v 인 에지가 모두 조건을 만족하도록 만들면 된다.
• 시간복잡도는 O(|E|)

"""Solution code for "BOJ 32925. Just Half is Enough".

- Problem link: https://www.acmicpc.net/problem/32925
- Solution link: http://www.teferi.net/ps/problems/boj/32925

Tags: [ad hoc]
"""

import sys
from teflib import psutils


@psutils.run_n_times
def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]

    inc_order_count = 0
    for _ in range(m):
        u, v = [int(x) - 1 for x in sys.stdin.readline().split()]
        if u < v:
            inc_order_count += 1

    if inc_order_count >= (m + 1) // 2:
        print(*range(1, n + 1))
    else:
        print(*reversed(range(1, n + 1)))


if __name__ == '__main__':
    main()