该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

排练名单

题目描述

学校即将举行文艺汇演，共有 $N$ 名同学报名参加排练。

其中有 $M$ 对同学存在意见分歧。若一对存在意见分歧的同学同时被选入排练名单，就会产生 $1$ 次冲突。

同一对同学至多只会产生 $1$ 次冲突。

老师最多能够处理 $K$ 次冲突。请你选择尽可能多的同学参加排练，使得被选同学之间产生的冲突总数不超过 $K$。

请你求出，最多可以选择多少名同学。

输入格式

第一行输入三个整数 $N,M,K$，分别表示报名参加排练的同学人数、存在意见分歧的同学对数，以及老师最多能够处理的冲突次数。

接下来 $M$ 行，每行输入两个整数 $u,v$，表示同学 $u$ 和同学 $v$ 之间存在意见分歧。

保证给出的关系互不重复，且满足 $1\le u<v\le N$。

数据范围

$1\le N\le 20$

$0\le M\le \dfrac{N(N-1)}{2}$

$0\le K\le M$

输出格式

输出一个整数，表示最多可以选择的同学人数。

输入输出样例 #1

输入 #1

6 6 2
1 2
1 3
2 3
4 5
4 6
5 6

输出 #1

4

输入输出样例 #2

输入 #2

5 4 0
1 2
1 3
1 4
1 5

输出 #2

4

说明/提示

样例1：

一种合法选择是选择同学 $1,2,4,5$。

此时产生的冲突为 $(1,2)$ 和 $(4,5)$，共 $2$ 次，没有超过老师能够处理的冲突次数。

可以证明，无法选择 $5$ 名同学。因为任意选择 $5$ 名同学时，都会完整选择到某个三人小组，而这个三人小组内部已经会产生 $3$ 次冲突，超过 $K=2$。