3497. 黑心的出租车

单点时限: 2.0 sec

内存限制: 256 MB

买完凤梨酥和椰子饼的 oxx 和 xjj,回到了宾馆,准备第二天的行程。

Xiamen 有 $n$ 个景点,标号为 $1,2,\ldots,n$。有些景点之间有旅游巴士往返。总共有 $k$ 条巴士线,第 $i$ 条巴士线在 $u_i,v_i$ 之间往返。Xiamen 的旅游巴士和其他地方不大一样:只有起点跟终点站,中间从来不停。并且,有趣的是,如果两个景点之间可以仅通过坐旅游巴士往返,在不走回头路的情况下,这条路径是唯一的。

严格地说,如果存在 $i_1,i_2,\ldots,i_s$,使得 $(u_{i_1},v_{i_1}),\ldots,(u_{i_s},v_{i_s})$ 构成一条 $a \leftrightarrow b$ 的简单路径,那么,这也是 $a \leftrightarrow b$ 的唯一一条简单路径。

问题在于,旅游巴士不一定能解决所有问题,因为居然有可能有两个景点根本不能通过旅游巴士相互到达!这时候,他们就不得不选择黑心的出租车。出租车可以在任意两个景点之间互相到达。遗憾的是,他们每乘一次出租车,就会被讹一笔……

如果能不乘出租车的话,当然是最好的。oxx 希望从宾馆出发游玩所有景点并且返回宾馆,在坐最少次数的出租车的前提下,乘最少次旅游巴士。

输入格式

第一行两个整数 $n$, $k$ ($2 \le n \le 10^5, 0 \le k \le 10^5$) 表示有 $n$ 个景点,$k$ 辆巴士。

接下去 $k$ 行,每行两个整数 $u_i,v_i$ $(1 \leq u_i,v_i \leq n, u_i \ne v_i)$,表示巴士往返通过的两个景点。无序点对 $(u_i,v_i)$ 在输入中出现至多一次。

$1$ 号景点为 oxx 所在宾馆。

输出格式

共一行两个整数分别表示 oxx 和 xjj 至少乘出租车的次数以及乘旅游巴士的次数。

样例

Input
4 2
1 3
2 4
Output
2 2
Input
3 1
1 2
Output
2 1

61 人解决,77 人已尝试。

68 份提交通过,共有 275 份提交。

4.0 EMB 奖励。

创建: 2 年,6 月前.

修改: 2 年,5 月前.

最后提交: 2 周,4 天前.

来源: EOJ Monthly 2018.2

题目标签