접촉 추적

새로운 감염병이 집단 안에서 퍼지기 시작했습니다. 감염되었을 수 있는 사람을 찾아 격리하도록 알려야 합니다. 이 질병의 특징은 다음과 같습니다.

• 감염자와 접촉한 사람은 감염될 수도 있고, 감염되지 않을 수도 있습니다. 감염되면 그날 남은 시간 동안은 감염성이 없으므로, 그날 다른 사람에게 옮기지 않습니다.
• 사람이 감염되면, 감염된 다음 날부터 감염성을 가집니다.
• 감염된 날로부터 2일 뒤부터 증상이 나타납니다. 이후 스스로 격리하며, 그때부터 누구와도 접촉하지 않습니다.

0일째에 신원을 알 수 없는 환자 제로 한 명이 감염되었습니다. 1일째에 환자 제로는 감염성을 가졌고 사람들과 접촉해 일부를 감염시켰을 수 있습니다. 2일째에 환자 제로는 증상이 나타나 접촉을 멈췄습니다. 하지만 1일째에 감염된 사람은 자신이 접촉하는 사람에게 질병을 계속 옮길 수 있습니다.

오늘은 $k$일째이며, 하루가 끝났습니다. 오늘을 포함해 날마다 서로 접촉한 모든 사람의 쌍 목록을 볼 수 있습니다. 내일 감염성은 있지만 아직 증상은 없는 사람, 즉 오늘 감염된 사람을 모두 찾아 격리하도록 알릴 수 있다면, 감염 확산을 멈출 수 있습니다. 내일 증상이 나타나는 사람은 스스로 격리하기 때문입니다. 확산을 확실히 멈추려면 격리하도록 알려야 하는 최소 인원을 구하세요.

첫 줄에 세 정수 $n$ ($1 \leq n \leq 1\,000$), $k$ ($1 \leq k \leq 10$), $c$ ($0 \leq c \leq 1\,000$)이 주어집니다. $n$은 사람의 수, $k$는 환자 제로가 감염된 뒤 지난 날의 수, $c$는 사람 사이의 접촉 횟수입니다.

이어지는 $c$개의 줄에는 세 정수 $a$, $b$ ($1 \leq a < b \leq n$), $d$ ($1 \leq d \leq k$)가 주어집니다. 이는 사람 $a$와 사람 $b$가 $d$일째에 접촉했음을 뜻합니다. 모든 줄은 서로 다릅니다. 1일 이후 접촉이 전혀 없는 사람이 최소 한 명 있습니다.

첫 줄에 $k+1$일째부터 격리하도록 알려야 하는 최소 인원 $x$를 출력합니다. 이어서 그 $x$명을 오름차순으로 한 줄에 한 명씩 출력합니다.

입력 예제 1에서 환자 제로는 사람 1 또는 사람 4일 수 있습니다. 사람 2와 사람 3은 환자 제로가 증상이 나타나 격리된 2일째에 접촉했으므로 제외할 수 있습니다.

사람 1이 환자 제로라고 가정합시다. 사람 1은 1일째에 사람 4를 감염시켰을 수 있습니다. 사람 1은 2일째에 증상이 나타나 격리를 시작하므로, 사람 1에서 사람 2나 사람 3으로 이어지는 접촉 경로는 없습니다. 따라서 사람 2와 사람 3은 안전합니다. 사람 4가 1일째에 감염되었다면 사람 4는 3일째에 증상이 나타나므로 연락할 필요가 없습니다. 환자 제로가 사람 1이라면 아무에게도 알릴 필요가 없습니다.

이번에는 사람 4가 환자 제로라고 가정합시다. 사람 4는 1일째에 사람 1을 감염시켰을 수 있으며, 같은 이유로 사람 1과 사람 4 모두 3일째에 알릴 필요가 없습니다. 남는 사람은 사람 2와 사람 3이며, 여기서는 여러 감염 경우를 살펴야 합니다.

사람 4가 1일째에 사람 2와 사람 3을 모두 감염시켰다면, 두 사람 모두 3일째부터 증상이 나타나 스스로 격리하므로 알릴 필요가 없습니다.

사람 4가 1일째에 사람 2는 감염시켰지만 사람 3은 감염시키지 않았다면, 사람 2는 2일째에 사람 3을 감염시킬 수 있습니다. 사람 3은 3일째에도 아직 증상이 없으므로, 사람 3에게 격리하도록 알려야 합니다.

마찬가지로 사람 4가 1일째에 사람 3은 감염시키고 사람 2는 감염시키지 않았다면, 사람 2에게 격리하도록 알려야 합니다.

따라서 감염 확산을 확실히 멈추려면 사람 2와 사람 3 모두에게 알려야 합니다. 이는 환자 제로가 사람 1이든 사람 4이든 성립합니다.