P16041 [ICPC 2022 NAC] Contact Tracing

一种新型传染病开始在人群中传播。你的任务是确定哪些人可能已被感染，以便让他们进行隔离。该疾病在人群中的传播方式如下： - 当一个人与感染者接触时，他有可能（但不一定）感染该疾病。如果他被感染，则在当天的剩余时间内不会具有传染性，因此不会传染给当天与他接触的其他人。 - 当一个人感染该疾病后，从感染的后一天开始具有传染性。 - 从感染的后两天开始，他会出现症状；因此，从那时起他会自我隔离，不再与任何人接触。 已知在第 $0$ 天，一个身份未知的 **零号病人** 感染了该疾病。在第 $1$ 天，他具有传染性，并可能与其他人接触，从而可能感染其他人。在第 $2$ 天，零号病人出现症状，因此不再与他人接触，但在第 $1$ 天被感染的人则可能将疾病传播给与他们接触的人。 今天是第 $k$ 天，并且今天已经结束。你掌握了一份记录，其中列出了每一天（包括今天）所有发生过接触的人员对。如果你能识别出所有明天可能具有传染性但尚未出现症状的人（即今天感染的人），并让他们进行隔离，那么疫情就能得到控制，因为所有明天出现症状的人都会自行隔离。为了确保疫情得到控制，你需要通知隔离的最少人数是多少？

输入的第一行包含三个整数 $n$（$1 \le n \le 1{,}000$）、$k$（$1 \le k \le 10$）和 $c$（$0 \le c \le 1{,}000$），其中 $n$ 表示人数，$k$ 表示自零号病人感染以来经过的天数，$c$ 表示人与人之间发生的接触次数。 接下来的 $c$ 行，每行包含三个空格分隔的整数 $a$、$b$（$1 \le a < b \le n$）和 $d$（$1 \le d \le k$），表示在第 $d$ 天，人员 $a$ 与人员 $b$ 发生了接触。所有这些 $c$ 行都是互不相同的。保证至少有一人在第 $1$ 天之后没有任何接触。

输出一行，包含一个整数 $x$，表示你必须通知其从第 $k + 1$ 天开始隔离的最少人数。随后输出 $x$ 行，每行一个人员编号，按升序列出必须隔离的人员。

### 样例输入 1 解释 在样例输入 1 中，零号病人可能是人员 $1$ 或人员 $4$。人员 $2$ 和 $3$ 可以被排除，因为他们是在第 $2$ 天发生接触，而此时零号病人已经出现症状并处于隔离状态。 假设人员 $1$ 是零号病人。人员 $1$ 可能在第一天感染了人员 $4$。人员 $1$ 在第 $2$ 天出现症状，因此开始隔离。所以，从人员 $1$（零号病人）到人员 $2$ 或 $3$ 没有接触链，因此人员 $2$ 和人员 $3$ 是安全的，无需隔离。如果人员 $1$ 在第 $1$ 天感染了人员 $4$，那么人员 $4$ 将在明天（第 $3$ 天）出现症状，因此无需通知他们，因为他们会自行隔离。因此，如果零号病人是人员 $1$，则无需通知任何人。 现在假设人员 $4$ 是零号病人。人员 $4$ 可能在第一天感染了人员 $1$；使用与上述相同的逻辑，无需在第 $3$ 天通知人员 $1$ 或人员 $4$ 进行隔离。剩下人员 $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$，这一措施都能保证控制住疫情。 翻译由 DeepSeek V3.2 完成