TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7851
  • 题目
  • P7851春游
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s 256MB
    问题描述

    果果的学校要举行春游活动,一共有 \(n\) 个人,一辆车最多可以载 \(k\) 个人。每个人要求和自己同乘一辆车的人必须是自己的朋友。朋友是双向关系,并且有传递性:如果 \(A,B\) 是朋友。\(B,C\) 是朋友,那么$A, C$也是朋友。现在给出了他们之间的 \(m\) 对朋友关系,请你计算至少需要多少辆车才可以载下所有人?

    输入格式

    第一行:\(n, m, k(1 \leq n \leq 10^5, 0 \leq m \leq 10^5, 1 \leq k \leq 10^9)\)

    接下来 \(m\) 行:每行一个 \(a, b\) 表示 \(a, b\) 是朋友关系。

    输出格式

    至少需要多少辆车才可以载下所有人。

    样例输入

    5 3 2
    1 2
    2 3
    3 4

    样例输出

    3