TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1283
  • 题目
  • P1283关系运算图
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    给出一有向图,图中每条边都被标上了关系运算符‘<’,‘>’,‘=’。现在要给图中每个顶点标上一个大于等于0,小于等于k的某个整数使所有边上的符号得到满足。若存在这样的k,则求最小的k,若任何k都无法满足则输出NO。
    例如下表中最小的k为2。
    结点1>结点2
    结点2>结点3
    结点2>结点4
    结点3=结点4
    如果存在这样的k,输出最小的k值;否则输出‘NO’。

    输入格式

    共二行,第一行有二个空格隔开的整数n和m。n表示G的结点个数,m表示G的边数,其中1<=n<=1000, 0<=m<=10000。全部结点用1到n标出,图中任何二点之间最多只有一条边,且不存在自环。
    第二行共有3m个用空格隔开的整数,第3i-2和第3i-1(1<=i<=m)个数表示第i条边的顶点。第3i个数表示第i条边上的符号,其值用集合{-1,0,1}中的数表示:-1表示‘<’, 0 表示‘=’, 1表示‘>’。

    输出格式

    仅一行,如无解则输出‘NO’;否则输出最小的k的值。

    样例输入


    4 4
    1 2 -1 2 3 0 2 4 -1 3 4 -1

    样例输出

    2