문제

역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.

세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.

# 1613
import sys
input = lambda : sys.stdin.readline().strip()
INF = int(1e9)

n, k = map(int, input().split())
graph_down = [[INF] * (n+1) for _ in range(n+1)]
graph_up = [[INF] * (n+1) for _ in range(n+1)]

for _ in range(k):
    a, b = map(int, input().split())
    graph_up[a][b] = 1
    graph_down[b][a] = 1
    
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph_down[a][b] = min(graph_down[a][b], graph_down[a][k] + graph_down[k][b])
            graph_up[a][b] = min(graph_up[a][b], graph_up[a][k] + graph_up[k][b])
            
s = int(input())
for _ in range(s):
    a, b = map(int, input().split())
    if graph_up[a][b] != INF:
        print("-1")
    elif graph_down[a][b] != INF:
        print("1")
    else:
        print("0")

백준 1613 역사