A85810.「SHOI 早期试题选」舞会

省选/NOI-

通过率:0%

时间限制:1.00s

内存限制:8MB

题目描述

某学校要召开一个舞会。现在已知在学校的所有 nn 名学生中,有些学生曾经互相跳过舞。(跳过舞的两个学生一定是一个男生和一个女生)。现在要求被邀请的学生中的任何一对男生女生互相都不能跳过舞,求这个舞会最多能够邀请多少学生参加。

输入格式

输入的第一行是 nnmm 。其中 nn 是可选的学生的总数,mm 是已知的跳过舞的学生的对数。
然后有 mm 行,分别包含两个非负整数,表示这两个编号的学生曾经跳过舞。其中,学生的编号从 00 号到 n1n-1 号。

输出格式

只要求输出一行,其中包含一个数字,即能够邀请的最大的学生数。

输入输出样例

  • 输入#1

    8 6
    0 2
    2 3
    3 5
    1 4
    1 6
    3 1

    输出#1

    5
  • 输入#2

    20 5
    5 2
    4 3
    18 17
    0 11
    13 3

    输出#2

    16

说明/提示

对于 100%100\% 的数据,n1000,m2000n \le 1000,m \le 2000

首页