A21238.校园网络【[USACO]Network of Schools加强版】

提高+/省选-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

nn 所学校 (1n10000)(1 \leq n \leq 10000) 已知他们实现设计好的网络共 mm 条线路,为了保证高速,网络是单向的。现在请你告诉他们至少选几所学校作为共享软件的母机,能使每所学校都可以用上。再告诉他们至少要添加几条线路能使任意一所学校作为母机都可以使别的学校使用上软件。

输入格式

第一行一个正整数 nn

接下来 nn 行每行有若干个整数,用空格隔开。

i+1i+1 行,每行输入若干个非零整数 xx,表示从 iixx 有一条线路。以 00 作为结束标志。

输出格式

第一行一个整数,表示至少选几所学校作为共享软件的母机,能使每所学校都可以用上。

第二行一个整数,表示至少要添加几条线路能使任意一所学校作为母机都可以使别的学校使用上软件。

输入输出样例

  • 输入#1

    5
    2 0
    4 0
    5 0
    1 0
    0
    

    输出#1

    2
    2

说明/提示

1n100001 \leq n \leq 10000, 边数 50000\le 50000

首页