BOJ - 14588 - Line Friends (Small)

import sys
_INF = 1e9

def check(x, y, vector):
    if vector[x][1] < vector[y][0] or vector[y][1] < vector[x][0]: return 0
    else: return 1

def solution():
    N = int(sys.stdin.readline())
    dist = [[_INF for _ in range(N)] for _ in range(N)]
    vector = []
    for i in range(N):
        dist[i][i] = 0

    for _ in range(N):
        L, R = map(int, sys.stdin.readline().split())
        vector.append((L, R))

    for i in range(N):
        for j in range(N):
            if check(i, j, vector):
                dist[i][j] = 1
                dist[j][i] = 1

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    Q = int(sys.stdin.readline())
    for _ in range(Q):
        A, B = map(int, sys.stdin.readline().split())
        print(-1 if dist[A-1][B-1] == _INF else dist[A-1][B-1])

solution()

https://www.acmicpc.net/problem/14588