Exits in Excess

• 주어진 방향 그래프에서 절반 이하의 에지를 제거해서 사이클이 없도록 만드는 문제.
• 가능한 방법은 다양하지만, 가장 간단하게 해결할 수 있는 방법은, 모든 u→v 에지중에서 u>v인 에지만 남기고 나머지를 지우면 이 그래프는 DAG가 된다. 만약 지워야 할 에지가 절반이 넘는다면, 반대로 u>v인 에지를 지우고 u<v 인 에지를 남기면 된다.
• 시간복잡도는 O(|E|)

"""Solution code for "BOJ 17546. Exits in Excess".

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

Tags: [ad hoc]
"""

import sys


def main():
    _n, m = [int(x) for x in sys.stdin.readline().split()]
    inc_order_edges, dec_order_edges = [], []
    for i in range(1, m + 1):
        u, v = [int(x) for x in sys.stdin.readline().split()]
        if u < v:
            inc_order_edges.append(i)
        else:
            dec_order_edges.append(i)

    answer = min((inc_order_edges, dec_order_edges), key=len)
    print(len(answer))
    print(*answer, sep='\n')


if __name__ == '__main__':
    main()