配点: 1000 点
問題文
作者太郎是N 我写了一本页小说。在这部小说中 有 M 连接,i 第二个连接是 A_i 页码和 B_i 页。
现在他正在写小说。 您正尝试将其分为 K 章节。如果我们将同一章节中存在的连接数视为“小说的质量”,那么小说质量的最大值是多少?
制約
- 所有输入均为整数
- 2 \leqq N \leqq 288
- 1 \leqq M \leqq 50
- 1 \leqq K \leqq 10
- K \leqq N
- 1 \leqq A_i < B_i \leqq N (1 \leqq i \leqq M)
入力
输入是按以下格式从标准输入给出的。
N M K A_1 B_1 \vdots A_M B_M
出力
标准输出的新颖质量最大值 请输出 1 请逐行输出。
入力例 1
6 4 3 3 4 3 5 2 5 1 6
出力例 1
3
入力例 2
4 6 1 1 2 1 3 1 4 2 3 2 4 3 4
出力例 2
6
入力例 3
10 4 10 1 3 2 4 2 3 1 4
出力例 3
0