3497. 黑心的出租车

单测试点时限: 2.0 秒

内存限制: 256 MB

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

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

严格地说,如果存在 ,使得 构成一条 的简单路径,那么,这也是 的唯一一条简单路径。

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

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

输入

第一行两个整数 , () 表示有 个景点, 辆巴士。

接下去 行,每行两个整数 ,表示巴士往返通过的两个景点。无序点对 在输入中出现至多一次。

号景点为 oxx 所在宾馆。

输出

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

样例

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

54 人解决,69 已尝试。

60 份提交通过,共有 241 份提交。

7.5 EMB 奖励。

创建: 10 月,2 周前.

修改: 10 月前.

最后提交: 1 周,1 天前.

来源: EOJ Monthly 2018.2

标签