TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  训练指南  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2207
  • 题目
  • P2207【2-SAT】和平委员会
    限制 : 时间限制 : 3000 MS   空间限制 : 65536 KB
    评测说明 : 每组0.1秒
    问题描述

    某国有n个党派,每个党派在议会中恰有2个代表。

    现在要成立和平委员会 ,该会满足:
    1.每个党派在和平委员会中有且只有一个代表
    2.如果某两个代表不和,则他们不能都属于委员会

    代表的编号从1到2n,编号为2i-1、2i的代表属于第i个党派
    求和平委员会是否能创立。若能,求一种构成方式。

    输入格式

    第一行,两个整数n(党派数),m(不友好对数)
    接下来m行,每行一对对两两不和的代表编号 a和b(1<=a<b<=2n)
    其中1≤n≤8000,0≤m ≤20000

    输出格式

    如果无法创立和平委员会,输出"NIE"
    否则输出一种方案,包含n行,每行一个数字表示一个代表的编号,按升序排列。
    若有多种方案,输出字典序最小的。

    样例输入 1

    3 2
    1 3
    2 4

    样例输出 1

    1
    4
    5

    样例输入 2

    3 4
    1 3
    1 4
    3 5
    2 6

    样例输出 2

    2
    4
    5

    提示

    2020.04.24更新: nodgd修复了数据的错误,并缩小时限卡掉了O(nm)算法。如果你的算法是O(nm)或者更高复杂度的,请到这里提交。


    来源  POI2001 Peaceful Commission HDU1814