문제
광기의 과학도시 자운에는 10억 개의 가로 도로와 10억 개의 세로 도로가 있다. 당신은 편의상 각 가로 도로와 세로 도로에 각각 순서대로 1~10억의 번호를 매기고, A번 가로 도로와 B번 세로 도로가 만나는 교차로를 (A, B)라고 정했다. 이웃한 두 도로 사이의 거리는 같기 때문에, 이웃한 두 도로 사이를 평범한 방법으로 이동한다면 도달 시간은 1로 일정하다.
신지드가 당신에게 화학 물질 배달을 의뢰하였다. 각 의뢰마다, (P, Q)에 있는 화학 물질을 (R, S)로 옮겨야 한다. 매 의뢰마다, 신지드는 당신을 (P, Q)로 바로 보내기 때문에 (P, Q)로 가는 데 걸리는 시간은 무시해도 좋다.
당신은 N개의 비밀 통로에 대해서 출입을 허가받았다. 각 비밀 통로는 (Pk, Qk)와 (Rk, Sk)를 연결하는데, 이 비밀 통로를 이용해서 두 지점 사이를 자유롭게 왕래가능하고, 이 때 1의 시간이 걸린다. 화학 물질을 빨리 배달하지 않으면 그 화학 물질에 중독될 수 있기 때문에, 가능한 빨리 배달하려고 한다. 신지드의 각 의뢰에 대해서 그 의뢰를 수행할 때 걸리는 최소 시간을 구하는 프로그램을 작성하여라. 단, 한 교차로에 두 개 이상의 비밀 통로가 있을 수 있다.
입력
첫 번째 줄에는 비밀 통로의 수 N과 신지드의 의뢰의 수 X가 주어진다. (1 ≤ N ≤ 150, 1 ≤ X ≤ 300) 두 번째 줄부터 N개의 줄에는 각 비밀 통로의 두 끝점의 위치를 나타내는 자연수 Pk, Qk, Rk, Sk 가 주어진다. (1 ≤ Pk, Qk, Rk, Sk ≤ 10억) N+2번째 줄부터 X개의 줄에는 신지드의 각 의뢰의 P, Q, R, S가 주어진다. (1 ≤ P, Q, R, S ≤ 10억)
출력
신지드의 각 의뢰에 대하여, 의뢰를 수행할 때 걸리는 최소 시간을 한 줄에 하나씩 출력한다. 답이 20억을 넘어갈 수 있으므로 유의하여라.
예제
3 4
1 3 5 3
3 2 4 5
5 1 2 4
2 1 5 5
9 1 1 9
1 2 4 3
3 4 5 6
4
11
3
4
로그인해야 코드를 작성할 수 있어요.