TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2102
  • 题目
  • P2102【并查集】烦人的生物
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    最后一题了,当然是要让我们的jz出场了(jz就是zj,zj就是jz,至于为什么……&),处于某种ws的对知识的渴望,jz非常喜欢生物。
    现在jz发现自己本身就是个非常纠结的动物,jz发现如果把自身的细胞排成一排,根据细胞某种性质的不同,可将细胞分成两类,如果将这两类细胞分别用0/1表示,就得到了一个能表示自身细胞的0/1串。jz发现了自身的0/1是个奇妙的东西,就决定出个题来恶心你。
    他会告诉你自身0/1串的长度m,和给出你的描述0/1串的语句条数n。
    每条语句都符合以下格式:
    a b even/odd
    表示自身 0/1串中第a~b位上数字的和是偶数/奇数
    jz想让你说出最早出现的与前面描述矛盾的语句是谁,你能解决这个问题吗?

    输入格式

    第一行,一个整数m,表示jz自身0/1串的长度
    第二行,一个整数n,表示jz给出的语句数目。
    第三行~,共n行,为jz给出的语句,保证按上文所述格式给出。

    输出格式

    输出zj最早说出的与前面语句矛盾的语句的位置-1
    Eg:如果该语句是第2句,输出1
    如果没有矛盾,则输出n

    样例输入

    10
    5
    1 2 even
    3 4 odd
    5 6 even
    1 6 even
    7 10 odd

    样例输出

    3

    提示

    40% m≤1000000
    100% m≤2100000000
    100% n≤5000


    来源  HZOI