TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3869
  • 题目
  • P3869排座位
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1s
    问题描述

    何老板的公司有一个圆形会议室,会议室里有一个环形会议桌,共2*n个座位。
    今天恰好有n位中国人和n位美国人来开会。为了表示尊重和平等,何老板要求美国人和中国人交替就座,也就是相邻两个人的国籍不能相同。
         但是,何老板发现,其中有些人有矛盾,挨在一起落座会不开心。

     何老板想知道,怎样安排座位,才能使得不开心的人数最少,请你帮他计算一下。

    输入格式

    第一行,两个整数n和m, n表示参会的人数为2*n, m表示其中有m对人有矛盾。
        接下来m行,每行两个整数x和y,表示编号为x的中国人和编号为y的美国人有矛盾。

    (中国人编号1到n,美国人编号也是1到n)

    输出格式

    一个整数,表示最少不开心的中国人的人数。

    样例输入 1

    3 4
    1 1
    1 2
    1 3
    2 1

    样例输出 1

    1

    样例输入 2

    3 7
    2 2
    1 2
    3 3
    1 1
    2 1
    2 3
    1 3

    样例输出 2

    2

    提示

    【数据范围】

     对于30% 的数据,0≤n≤5

     对于 100% 的数据,0≤n≤9 , 0≤m≤n*n


    来源  改编自multi 2016 necklace