第 2 场 AtCoder Beginner Contest
派系AI (CI翻译)
N
M
(x,\ y)
(x,\ y)
x
y
N
N M
x_1 y_1
x_2 y_2
:
x_M y_M$1$行目には、高橋くん以外の国会議員の数$N\ (1≦N≦12)$と、人間関係の数$M$$(0≦M≦N(N-1)/2)$が半角空白区切りで与えられる。$2$行目から$M+1$行目までの$M$行で、人間関係が与えられる。
1
5 3
1 2
2 3
1 3$1$行目：$5$人の議員と$3$つの人間関係が存在する。$2$行目：議員$1$と議員$2$は知り合いである。$3$行目：議員$2$と議員$3$は知り合いである。$4$行目：議員$1$と議員$3$は知り合いである。
3- 議員
$1$、議員$2$、議員$3$は互いに知り合いなので、この$3$人は派閥を構成することができる。
5 3
1 2
2 3
3 42- 議員数
$2$の派閥として の$3$通りが考えられます。 - 議員
$1$と議員$2$の派閥- 議員
$2$と議員$3$の派閥 - 議員
$3$と議員$4$の派閥
- 議員
7 9
1 2
1 3
2 3
4 5
4 6
4 7
5 6
5 7
6 7412 01题目描述
高桥君是一名国会议员，同时也是派系的领袖。
国会议员之间存在各种人际关系。每种人际关系表示为“议员 $x$ 与议员 $y$ 互相认识”。
派系是指满足以下条件的议员集合：派系中的任意两名议员都互相认识。
现给出高桥君以外的国会议员人数以及他们之间的人际关系。请你求出仅由高桥君以外的议员组成的派系的最大人数。
约束条件
$1≦N≦12$$0≦M≦N(N-1)/2$$1≦x_i<y_i≦N$- 不会给出重复的人际关系。
输入格式
输入由标准输入给出，格式如下：
N M
x_1 y_1
x_2 y_2
:
x_M y_M- 第
$1$行以半角空格分隔给出除高桥君以外的国会议员人数$N$$(1≦N≦12)$与人际关系数$M$$(0≦M≦N(N-1)/2)$。 - 从第
$2$行到第$M+1$行的$M$行中，给出人际关系。
输出格式
输出由标准输出给出。输出能够组成的派系的最大人数。
样例
样例 1
5 3
1 2
2 3
1 3- 第
$1$行：存在$5$名议员和$3$条人际关系。 - 第
$2$行：议员$1$与议员$2$互相认识。 - 第
$3$行：议员$2$与议员$3$互相认识。 - 第
$4$行：议员$1$与议员$3$互相认识。
3- 议员
$1$、议员$2$、议员$3$互相认识，因此这$3$人可以组成一个派系。
样例 2
5 3
1 2
2 3
3 42- 人数为
$2$的派系共有$3$种可能：- 议员
$1$和议员$2$组成的派系 - 议员
$2$和议员$3$组成的派系 - 议员
$3$和议员$4$组成的派系
- 议员
样例 3
7 9
1 2
1 3
2 3
4 5
4 6
4 7
5 6
5 7
6 74样例 4
12 01题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。