TouchStone
  Please Login
Login Sign Up
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P7851
  • Problem
  • P7851春游
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s 256MB
    Description

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

    Input Format

    第一行:\(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\) 是朋友关系。

    Output Format

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

    Sample Input

    5 3 2
    1 2
    2 3
    3 4

    Sample Output

    3