#G1040. [GESP202403 七级] 交流问题

[GESP202403 七级] 交流问题

[GESP202403 七级] 交流问题

题目描述

来自 2 所学校 A 校、B 校的 NN 名同学相聚在一起相互交流,方便起见,我们把这些同学从 11 至 NN 编号。他们共进行了 MM 次交流,第 ii 次交流中,编号为 ui,viu_i, v_i 的同学相互探讨了他们感兴趣的话题,并结交成为了新的朋友。

由于这次交流会的目的是促进两校友谊,因此只有不同学校的同学之间会交流,同校同学并不会相互交流。

作为 A 校顾问,你对 B 校的规模非常感兴趣,你希望求出 B 校至少有几名同学、至多有几名同学。

输入格式

第一行两个正整数 N,MN, M,表示同学的人数,交流的次数。

接下来 MM 行,每行两个正整数 ui,viu_i, v_i,表示一次交流。

题目保证输入合法,即交流一定是跨校开展的。

输出格式

输出一行两个整数,用单个空格隔开,分别表示 B 校至少有几名同学、至多有几名同学。

样例 #1

样例输入 #1

4 3
1 2
2 3
4 2

样例输出 #1

1 3

样例 #2

样例输入 #2

7 5
1 2
2 3
4 2
5 6
6 7

样例输出 #2

2 5

数据范围

测试点 数据范围 说明
1~3 N≤17N ≤ 17,M≤50M ≤ 50 占 30%
4~6 N≤500N ≤ 500,M≤2000M ≤ 2000 占 60%
全部 N≤105N ≤ 10^5,M≤2×105M ≤ 2 \times 10^5 全部数据