너무 졸려 | cho.sh

문제

오늘 친구와 만나기로 했는데, 어젯밤에 잠을 제대로 못 자서 너무 졸리다.

약속 장소가 있는 역까지 기차로 가니까 기차 안에서 잘 수 있다. 기차에 타는 순간 잠들어서 내릴 때까지 계속 자는데, 목적지에 도착할 때까지 기차 한 대에서만 잘 수 있다.

기차 시간표와 출발역, 출발 시각, 약속 역, 약속 시각이 주어진다. 약속 시각까지 약속 역에 도착한다는 조건을 지키면서 기차 안에서 잘 수 있는 가장 긴 시간을 구하는 프로그램을 작성하시오.

입력

입력은 데이터 세트 여러 개로 이루어진다. 각 데이터 세트의 형태는 다음과 같다.

S T
D TimeD A TimeA
N1
K(1,1) Time(1,1)
...
K(1,N1) Time(1,N1)
N2
K(2,1) Time(2,1)
...
K(2,N2) Time(2,N2)
...
NT
K(T,1) Time(T,1)
...
K(T,NT) Time(T,NT)

첫째 줄에는 역의 수 $S$ 와 기차의 수 $T$ 가 주어진다 ( $1 \le S \le 1000$ , $0 \le T \le 100$ ). 둘째 줄에는 출발역 D, 출발 시각 TimeD, 약속 역 A, 약속 시각 TimeA가 순서대로 주어진다. 그 다음에는 기차 $T$ 대의 시간표가 이어진다. $i$ 번째 시간표의 첫째 줄에는 그 기차가 정차하는 역의 수 Ni가 주어지고, 이어지는 Ni개의 줄에는 역 번호 K(i,j)와 그 역에 정차하는 시각 Time(i,j)가 주어진다.

역 번호는 1 이상 $S$ 이하의 정수다. 시각은 hh:mm 형식이며, hh는 00부터 23까지, mm은 00부터 59까지다.

입력의 마지막 줄에는 0이 두 개 주어진다.

다음을 가정해도 된다.

모든 기차는 역 두 개 이상에 정차한다.
한 기차가 같은 역에 두 번 정차하는 일은 없다.
기차가 한 역에서 다음 역까지 가는 데 최소 1분이 걸린다.
한 데이터 세트에 나오는 시각은 모두 같은 날의 시각이다.
환승은 즉시 끝나므로, 어떤 역에 도착한 바로 그 시각에 출발하는 기차에 탈 수 있다.

출력

각 데이터 세트마다 한 줄씩 출력한다. 약속 시각까지 약속 역에 도착할 수 있으면 잘 수 있는 최대 시간을 분 단위로 출력하고, 도착할 수 없으면 impossible을 출력한다. 역에서 기다리는 시간과 기차에서 깨어 있는 시간은 자는 시간에 넣지 않으며, 한숨도 자지 않고 가는 경우는 0분이다.