TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2350
  • 题目
  • P2350【2-SAT】False or True
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    平面上,一个圆,圆的边上按顺时针放着n个点。现在要连m条边,比如a,b,那么a到b可以从圆的内部连接,也可以从圆的外部连接。给你的信息中,每个点最多只会连接的一条边。问能不能连接这m条边,使这些边都不相交。(比如两条边分别是1−2,2−3,则可以连接。若有三条边分别时1−5,2−6,3−7则一定会出现相交)。
    输入数据会有多组:防止骗分
    对于每一组输入数据,如果可以存在的话,则输出true,如果不能存在的话,则输出false

    输入格式

    第一行一个数q,表示数据的组数。
    对于每组数据,第一行为两个数n和m,n指点的个数,m指要连的边的个数
    2..m+1行,每行两个数字a,b表示要连的边的两个端点

    输出格式

    若可以,则输出true,否则,输出false

    样例输入

    1
    4 2
    0 1
    3 2

    样例输出

    true

    提示

    q<=30,n<=1000,m<=100


    来源  HZOI