序列判定
测试数据来自 system/1671
背景
做题目前,讲一个寓言。
有一对兄弟,他们的家住在80层楼上。有一天他们外出旅行回家,发现大楼停电了!虽然他们背着大包的行李,但看来没有什么别的选择,于是哥哥对弟弟说,我们就爬楼梯上去!于是,他们背着两大包行李开始爬楼梯。爬到20楼的时候他们开始累了,哥哥说“包包太重了,不如这样吧,我们把包包放在这里,等来电后坐电梯来拿。”于是,他们把行李放在了20楼,轻松多了,继续向上爬。
他们有说有笑地往上爬,但是好景不长,到了40楼,两人实在累了。想到还只爬了一半,两人开始互相埋怨,指责对方不注意大楼的停电公告,才会落得如此下常他们边吵边爬,就这样一路爬到了60楼。到了60楼,他们累得连吵架的力气也没有了。弟弟对哥哥说,“我们不要吵了,爬完它吧。”于是他们默默地继续爬楼,终于80楼到了!兴奋地来到家门口兄弟俩才发现他们的钥匙留在了20楼的包包里了。
下面开始做题。
描述
给出M个三元组(a,b,c),表示a~b中最小值为c.
找出最小的I满足:存在N长序列满足1~I-1中所有的三元组的要求,并且不存在N长序列满足1~I中所有的三元组的要求,若存在N长序列满足所有三元组要求,输出0。
格式
输入格式
第一行两个整数n,m
接下来m行,每行一个三元组(a,b,c);
保证1<=n<=10^6 0<=m<=50000 a<=b a+500>=b 0<=c<=n
输出格式
一个数,如题
样例1
样例输入1
20 4
1 10 7
5 19 7
3 12 8
11 15 12
样例输出1
3
限制
各个测试点1s
提示
From usaco 2008.