Problem10672--洛谷P10378 - [GESP七级] [202403]交流问题

10672: 洛谷P10378 - [GESP七级] [202403]交流问题

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

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

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

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

Input

第一行两个正整数,表示同学的人数 $n$、交流的次数 $m$。  
接下来 $m$ 行,每行两个整数 $u_i, v_i$,表示一次交流。

Output

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

Constraints

对 $30\%$ 的数据,保证 $n \leq 17$,$m \leq 50$。
对 $60\%$ 的数据,保证 $n \leq 500$,$m \leq 2000$。
对全部的测试数据,保证 $1 \leq u_i, v_i \leq n \leq 10^5$,$1 \leq m \leq 2\times 10^5$,输入是合法的,即交流一定是跨校开展的。

Sample 1 Input

4 3
1 2
2 3
4 2

Sample 1 Output

1 3

Sample 2 Input

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

Sample 2 Output

2 5

HINT

洛谷P10378

Source/Category