2차원 평면상에 m개의 수직선과 n개의 수평선으로 이루어진 격자 형태의 도로망이 있다.

아래 그림은 7개의 수직선과 6개의 수평선으로 이루어진 도로망의 예이다.

수직선과 수평선이 만나는 교차점들 중 가장 왼쪽 아래 점의 위치는 (1,1)이고, 가장 오른쪽 위 점의 좌표는 (m,n)이다.

이 도로망을 운행하는 버스들이 k개 있고, 각 버스는 하나의 수평선 상의 두 교차점 사이 선분이나 하나의 수직선 상의 두 교차점 사이 선분을 왕복 운행한다.

각 버스는 운행하는 선분 사이의 모든 교차점(선분의 양 끝 교차점 포함)에서 정차한다.

버스 회사의 규정 상 환승은 딱 한 번 가능하고, 버스의 노선 상 겹치는 위치가 있는 경우 가능하다.

두 버스의 번호 x와 y가 주어졌을 때, x버스에서 y버스로 갈아타는 것이 가능한지 출력하는 프로그램을 작성하시오.

예를 들어, 8대의 버스가 다음과 같이 운행한다고 하자.

1번 버스: (2, 1) - (2, 2)
2번 버스: (1, 1) - (5, 1)
3번 버스: (3, 2) - (6, 2)
4번 버스: (5, 6) - (5, 1)
5번 버스: (1, 5) - (7, 5)
6번 버스: (7, 3) - (7, 6)
7번 버스: (2, 1) - (2, 6)
8번 버스: (3, 5) - (6, 5)

현재 타고 있는 버스 x=2번 버스이고 갈아타고 싶은 버스가 y=4번 버스라고 하자.

2번 버스를 타고 교차점 (5, 1)에서 내려, 4번 버스를 타면 갈아타는 것이 가능하다.

x = 8 이고, y=5 인 경우 (5, 5)에서 갈아타면 되기에 이 또한 가능하다.

하지만, x = 3 이고, y = 6인 경우 서로 교차하는 위치가 없기에 갈아타는 것이 불가능하다.

쉬운 버스 갈아타기 timer 1s memory 32MB

쉬운 버스 갈아타기 1s 32MB