A29191.失败的五子棋
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
你由于昨天玩五子棋连跪四把,你的好朋友 Macw 认定你的推理能力还需要多多锻炼。因此,Macw 绞尽脑汁过后想出来一道看似简单其实不难的推理题目旨在于提高你的逻辑思维能力。题目如下:
有一个长度为 N 的序列 S,序列中的数字不是 1 就是 2。但你不知道这个序列的具体内容,但你知道存在在这个序列中的 M 组关系。每组关系可以用一个三元组 (Ai,Bi,Ci) 来表示,表示序列 SAi+SBi+Ci 的和是一个偶数。
Macw 想考考你,你至少需要知道这个序列的几个数字才可通过这 M 条关系推导出整个序列。
Problem Credits: Macw07。
输入格式
第一行输入两个整数 N 与 M。
接下来的 M 行,每一行输入三个整数 Ai,Bi,Ci。
输出格式
输出一个整数,表示答案。
输入输出样例
输入#1
6 5 1 2 1 2 3 2 1 3 3 4 5 4 5 6 5
输出#1
2
输入#2
100000 1 1 100000 100
输出#2
99999
说明/提示
数据范围与约定:
- 对于 100% 的数据,满足 2≤N≤105。
- 对于 100% 的数据,满足 1≤M≤105。
- 对于 100% 的数据,满足 1≤Ai,Bi≤N。
- 对于 100% 的数据,满足 1≤Ci≤100。
- 对于 100% 的数据,保证数据均合法。