열차 시간표

1번부터 n번까지 번호가 매겨진 n개의 도시를 잇는 철도망을 운영하고 있습니다. 각 열차는 정해진 시간표에 따라 (항상 정시에) 출발역에서 도착역까지 중간에 어디에도 정차하지 않고 곧바로 운행합니다. 각 역에는 출발 시간표가 있으며, 시간표에는 직행 편만 적혀 있습니다.

도시 p에서 도시 q로 가려는 승객은 직행에만 얽매이지 않고 열차를 갈아탈 수 있습니다. 환승에는 시간이 전혀 걸리지 않지만, 지금 타고 있는 열차가 도착하기 전에 출발하는 열차로는 갈아탈 수 없습니다.

승객들은 모든 최적 연결의 시간표를 원합니다. 도시 p를 시각 A에 출발하여 도시 q에 시각 B에 도착하는 연결이 최적이라는 것은, p를 A보다 이르지 않게(시각 A 이상) 출발하여 q에 B보다 늦지 않게(시각 B 이하) 도착하는 다른 연결이 존재하지 않는다는 뜻입니다. 우리는 하루 안에 마칠 수 있는 연결만 고려합니다.

다음을 수행하는 프로그램을 작성하세요.

• 표준 입력에서 n과 n개 도시 각각의 출발 시간표를 읽고,
• 도시 1에서 도시 n으로 가는 최적 연결들의 시간표를 만들어,
• 답을 표준 출력에 씁니다.

첫째 줄에 정수 n (2 ≤ n ≤ 100000)이 주어집니다. 이어서 도시 1, 2, …, n의 시간표가 이 순서대로 주어집니다.

각 시간표의 첫 줄에는 정수 m 하나가 주어집니다. 이어지는 m개의 줄은 각각 시간표의 한 항목을 나타내며, 출발 시각 A, 도착 시각 B (A < B), 도착 도시 번호 t (1 ≤ t ≤ n)가 공백 하나로 구분되어 주어집니다. 시각 A와 B는 hh:mm 형식이며, hh는 시를 나타내는 두 자리 숫자 (00 ≤ hh ≤ 23), mm은 분을 나타내는 두 자리 숫자 (00 ≤ mm ≤ 59)입니다. 한 시간표 안의 항목들은 출발 시각 기준 비내림차순으로 주어집니다. 모든 시간표의 항목 수의 합은 1000000을 넘지 않습니다.

첫째 줄에 답이 되는 시간표의 항목 수 r을 출력합니다. 이어지는 r개의 줄에는 각각 출발 시각 A와 도착 시각 B를 공백 하나로 구분하여 출력합니다. 시각 형식은 입력과 같아야 하며, 항목들은 출발 시각 기준 오름차순으로 정렬해야 합니다. 출발 시각과 도착 시각이 모두 같은 최적 연결이 여러 개라면 그중 하나만 출력합니다.