문제

수직선 위에 N개의 선분들이 살고 있다. N개의 선분들은 서로 친구 관계를 맺기 시작했다.

선분들 중 오직 영역이 겹치는 선분끼리만 대화를 할 수 있었기 때문에 이들끼리만 친구가 되었다. 위 그림을 참고하면 브라운과 코니는 친구가 되었고 문과 제임스도 친구가 되었지만 브라운과 샐리는 친구가 되지 못했다.

N개의 선분들은 갑자기 자신들이 얼마나 가까운 사이인지 확인해보려고 한다. 문과 레너드는 친구가 아니지만, 제임스가 문과 레너드와 친하므로 문은 레너드의 친구의 친구이다. 비슷하게, 브라운은 샐리의 친구의 친구의 친구의 친구이다. 일반적인 친구 관계를 1만큼 가깝다고 하면, 문과 레너드는 2만큼 가깝고, 브라운과 샐리는 4만큼 가깝다. 문은 코니의 친구의 친구지만, 코니의 친구이기도 하므로 문과 코니는 1만큼 가깝다.

선분 마을의 시장인 당신은, 두 명의 선분이 ‘우리가 얼마나 가까운 사이야?’라고 물어볼 때마다 바로 ‘너희 둘은 OO만큼 가까워’라고 답해야 한다. 당신은 이 업무를 자동화해서 수행해주는 프로그램을 작성해야 한다.

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

n = int(input())
line = [[] for _ in range(n)]

graph = [[INF] * (n+1) for _ in range(n+1)]

for i in range(n):
    line[i] = list(map(int, input().split()))
    
for i in range(n):
    for j in range(n):
        if line[i][0] <= line[j][0] <= line[i][1] or line[i][0] <= line[j][1] <= line[i][1]:
            graph[i+1][j+1] = 1
            graph[j+1][i+1] = 1
            
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
            
q = int(input())
for _ in range(q):
    A, B = map(int, input().split())
    if graph[A][B] == INF:
        print("-1")
    else:
        print(graph[A][B])

백준 14588 Line Friends (Small)