버스 노선 배포 점검

문제

버스 운행 정보를 제공하는 시스템에서 각 노선의 안내 프로그램을 별도로 배포한다. DevOps 담당자는 배포가 끝난 뒤 수집한 버전 목록과 의존성 목록을 대조하여 추가 점검이 필요한 노선을 찾으려 한다. 노선에는 1부터 N까지의 번호가 붙어 있으며, 각 노선에는 안내 프로그램이 정확히 하나 설치되어 있다. 버전은 점으로 구분한 세 정수 a.b.c로 나타낸다. 두 버전을 비교할 때는 a를 먼저 비교하고, a가 같으면 b를 비교하며, a와 b가 모두 같으면 c를 비교한다. 처음으로 다른 위치의 정수가 큰 버전이 더 높은 버전이다. 세 정수가 모두 같으면 같은 버전이다. 예를 들어 3.2.0은 3.1.99보다 높다. 버전 전체를 문자열의 사전 순서나 소수로 해석해서는 안 된다. 각 의존성 기록은 출발 노선 s, 참조 노선 t, 요구 버전 v로 이루어진다. 이는 s번 노선의 안내 프로그램이 정상적으로 동작하려면 t번 노선에 설치된 버전이 v 이상이어야 한다는 뜻이다. 참조 노선의 설치 버전이 요구 버전보다 낮으면 그 기록을 만족하지 못한 것으로 판단한다. 같은 두 노선에 관한 기록이 여러 번 등장할 수 있으며, 각 기록을 독립적으로 검사한다. 하나 이상의 기록을 만족하지 못한 출발 노선을 점검 대상으로 정한다. 의존성 기록이 없는 노선은 점검 대상이 아니다. 참조 노선이 점검 대상이라는 사실만으로 출발 노선을 추가하지는 않는다. 검사에는 처음 주어진 설치 버전만 사용하며, 검사 중 설치 버전을 바꾸거나 의존성을 연쇄적으로 전파하지 않는다. 점검 대상 노선의 수와 번호를 구하는 프로그램을 작성한다. 같은 노선이 여러 기록을 만족하지 못하더라도 결과에는 한 번만 포함한다. 노선 번호는 오름차순으로 출력하며, 점검 대상이 없으면 그 수인 0만 출력한다.

입력

첫째 줄에 정수 N과 M이 주어진다. 1≤N≤12,000, 0≤M≤12,000이다.
다음 N개 줄에는 1번부터 N번까지 각 노선의 설치 버전이 하나씩 주어진다.
다음 M개 줄에는 정수 s, t와 요구 버전 v가 공백으로 구분되어 주어진다. 1≤s,t≤N이며 s=t도 가능하다.
모든 버전은 a.b.c 형식이다. a, b, c는 각각 0 이상 99 이하의 정수이며, 0을 제외한 정수에는 앞에 불필요한 0이 붙지 않는다.

출력

첫째 줄에 점검 대상 노선의 수를 출력한다. 그 수가 양수이면 둘째 줄에 점검 대상 노선 번호를 오름차순으로 공백으로 구분하여 출력한다. 그 수가 0이면 둘째 줄을 출력하지 않는다.

4 5
1.4.0
2.0.0
1.3.9
0.9.8
1 2 1.99.99
2 3 1.4.0
4 1 1.4.0
2 4 0.9.9
3 3 1.3.9

1
2

2 2
3.2.0
3.1.99
1 2 3.1.99
2 1 3.1.99

0

출처: Devin.KR 자체 제작