$m \times n$ 격자배열로 방이 배치된 건물이 있다. 각각의 방은 이웃한 방과 항상 하나의 문으로 연결되어 있다. 이 건물의 밖으로 통하는 출입문은 오직 북동쪽 코너에 있는 방에만 나있다. 이 출입문은 밖으로 나갈 때나 안으로 들어올 때나 $mn$개의 열쇠를 모두 이용해야 열리는 정밀한 자물쇠로 잠겨있는데, 각각의 열쇠는 각각의 방마다 하나씩 배치되어있다. 남서쪽 끝방에 한 사람이 있고 이웃한 방으로 이동해갈 것이다. 처음에는 모든 방과 방 사이의 문이 열려있었지만, 이 사람이 방을 떠날 때마다 그 방의 모든 문이 자동적으로 잠긴다. 이 사람이 모든 열쇠를 다 모아서 건물을 빠져나갈 수 있는 $(m,n)$쌍을 모두 구하여라.