99011 - 朋友

通过次数

41

提交次数

123

Time Limit : 1 秒
Memory Limit : 128 MB

经过六年的努力,小明终于被一所知名中学录取。优秀的小明总是对一些奇奇怪怪的事情感兴趣,这次他想知道谁在这所新学校拥有的朋友最多,由于大家都才刚报到,所以小明只知道大家两两之间是否是朋友关系。

Input

第一行有两个整数n和m,n表示总人数,m表示总关系数。 接下来m行,每行有2个以空格隔开的整数a和b,表示a和b是朋友,a和b均为1到n之间的整数。不会给出重复的朋友关系。

Output

仅有一行,表示朋友数最多的人所拥有的朋友,每两个整数之间用空格隔开,按照字典序从小到大输出。如果存在多个人朋友数都是最多的情况,请输出字典序最小的那人的答案,具体见样例。

Examples

Input

3 3
1 2
2 3
1 3

Output

2 3

Hint

50%的数据,1 <= n <= 10 80%的数据,1 <= n <= 1000 100%的数据,1 <= n <= 10000,m <= 500000