← 返回题目列表

AtCoder · tessoku_book_fj

C12. 小说家太郎

中文机器翻译题面 查看原题

配点: 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