문제

N명의 학생들이 키 순서대로 줄을 서려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 각 학생이 설 수 있는 위치의 범위를 구하는 프로그램을 작성하시오.

# 2273
import sys
input = lambda : sys.stdin.readline().strip()
INF = sys.maxsize

n, m = map(int, input().split())
graph_front = [[0] * (n+1) for _ in range(n+1)]
graph_back = [[0] * (n+1) for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph_front[a][b] = 1
    graph_back[b][a] = 1
    
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            if graph_front[a][k] and graph_front[k][b]:
                graph_front[a][b] = 1
            if graph_back[a][k] and graph_back[k][b]:
                graph_back[a][b] = 1
            
for i in range(1, n+1):
    graph_front[i][i] = 0
    graph_back[i][i] = 0
    
for i in range(1, n+1):
    for j in range(1, n+1):
        if graph_front[i][j] and graph_back[i][j]:
            print("-1")
            exit(0)
            
for i in range(1, n+1):
    front, back = 0, 0
    for j in range(1, n+1):
        if graph_front[i][j]:
            front += 1
        elif graph_back[i][j]:
            back += 1
    start, end = 1 + back, n - front
    print(start, end)

백준 2273 줄 서기