시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB111100.000%

문제

There are empty plastic glasses marked with numbers from 1 to N which can be put one into another, standing on the table.

You are given number of moves a→b that mean that you should move the bunch containing glass a to the bunch containing glass b. If a is equal to b, or glasses a and b are in the same bunch, than that move does nothing.

For example, we have 7 glasses and moves 1→3, 2→6, 3→6, 4→7 and 4→2, then situation on the table will change as follows:

                                                                        4
                                                                        7
                                                    1         1         1
                                                    3         3         3
                    1             1     2           2         2 4       2
1 2 3 4 5 6 7 --> 2 3 4 5 6 7 --> 3 4 5 6 7 --> 4 5 6 7 --> 5 6 7 --> 5 6

Moves must be made in the given order.

Write a program that will choose zero move, which is move that should be made before the first move in the given order. You should choose such zero move that will maximize the number of glasses in the largest bunch.

입력

In the first line of input there are two integers N and M, 2 ≤ N ≤ 10000, 0 ≤ M ≤ 100000. N is the number of glasses standing at the table and M is the number of moves to be made.

Next M lines contain moves to be made. In each of those lines are two integers a and b which represent move a→b.

출력

One and only line of output file should contain zero move a→b represented by two integers a and b separated by one space.

Note: solution need not to be unique.

예제 입력 1

5 3
1 2
5 3
4 1

예제 출력 1

4 5

예제 입력 2

6 4
5 2
3 3
1 3
6 2

예제 출력 2

3 5

예제 입력 3

10 9
3 7
5 9
10 10
9 5
8 7
3 7
6 1
4 2
2 6

예제 출력 3

7 2