徐老师的刑事审讯
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
最近警察局在一次抓捕行动中抓到了一大批嫌疑人，这批嫌疑人中存在两种人，一种是犯罪团伙的罪犯，一种是被犯罪团伙抓来做苦力的可怜人
徐老师作为专业的侦探，自然要帮助警方找到坏人
现在警方已经对其中一部分人进行了审讯，得到了 $m$ 条供认线索
第 $i$ 条供认线索由 $3$ 个信息 $x_i,y_i,z_i$ 组成
若 $z_i$ 为 $0$，则表示编号为 $x_i$ 的人指认编号为 $y_i$ 的人为犯罪团伙之一
若 $z_i$ 为 $1$，则表示编号为 $x_i$ 的人指认编号为 $y_i$ 的人为被抓来的可怜人
而徐老师经过仔细的观察，他发现罪犯一定说的是假话，而可怜人说的一定是真话
现在警方对这 $m$ 条供认线索进行了排序，而这 $m$ 条线索有点多，不利于警方追查罪犯
所以现在警方想知道，第几条线索开始出现了矛盾？这样警方就可以以这部分出现矛盾发言的人会突破口追查罪犯了
这里的矛盾指无法找到一种可能的身份分配，使得所有人的供认线索都符合情况
当然，如果所有线索均不存在矛盾，那么说明警方需要继续审讯嫌疑人，请你输出 `Continue`
输入格式
第一行包含两个整数 $n,m$ 表示有 $n$ 个嫌疑人，警方已经得到了 $m$ 条供认线索
接下来的 $m$ 行每行包含三个整数 $x_i,y_i,z_i$，含义如题
对于 $15\%$ 的数据，$n \leq 20$，$m \leq 50$；
对于 $30\%$ 的数据，$n \leq 5 \times 10^2$，$m \leq 10^3$；
对于 $50\%$ 的数据，$n \leq 2 \times 10^3$，$m \leq 10^5$；
对于另外 $10\%$ 的数据，满足 $z == 1$
对于 $100\%$ 的数据，$1 \leq n,m \leq 2 \times 10^5$，$x_i,y_i\in\{1,2,\cdots n\}, z_i \in \{0,1\}$
输出格式
若某条供认线索出现了矛盾，则输出第一次出现矛盾的供认线索编号
若所有线索均不存在矛盾，请输出 `Continue`
样例
4 3
1 2 1
3 4 0
2 1 032023暑CSP-S复赛集训模拟赛六
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-8-2 22:15
- 结束于
- 2023-8-12 22:15
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 15
