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

题目背景

浙江省的几所 OI 强校的神犇发明了一种人工智能,可以 AC 任何题目,所以他们决定建立一个网络来共享这个软件。但是由于他们脑力劳动过多导致全身无力身体被♂掏♂空,他们来找你帮助他们。

题目描述

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

输入格式

输出格式

说明/提示

~~POJ 原题。数据扩大了 $100$ 倍。~~ ~~$1 \leq $ 边数 $\leq 5000000$,$1 \leq n \leq 10000$ 。~~ 实际上,$1 \leq n \leq 10000$,$1\le $ 边数 $\le 50000$。