Unlike normal cats, Mimi adores the rich taste of carrots. In order to obtain more delectable, fresh carrots, Mimi has decided to invade the Land of the Carrots! The Land of the Carrots has 
~N~ cities, numbered 
~1, 2, \dots, N~, with 
~M~ bidirectional roads connecting pairs of cities such that it is possible to travel from any city to another. As a master of graph theory, Mimi knows that there may exist city 
~A~ such that blockading ~A~, or disconnecting all the roads to ~A~, will break the Land of the Carrots into at least 
~3~ disjoint graphs, or provinces (including ~A~). Among these provinces, the resistance 
~R~ Mimi will encounter is the maximum size of any one province. Mimi wants to find city 
~B~ such that blockading it will minimize ~R~, so the least amount of effort is required for her to conquer the Land of the Carrots. Could you help her out?
Constraints
Subtask 1 [20%]
~1 \le N \le 1\,000~
~1 \le M \le 5\,000~
Subtask 2 [80%]
~1 \le N \le 100\,000~
~1 \le M \le 500\,000~
Input Specification
The first line of input will contain 2 integers, ~N~ and ~M~, separated by a space.
The next ~M~ lines will each contain 2 integers 
~u~ and 
~v~, which means there exists a bidirectional road between cities ~u~ and ~v~.
Output Specification
2 integers separated by a space, ~B~ and ~R~. In the event of a tie, print the city with the largest number. If no such city exists, output -1 for both values.
Sample Input 1
4 4
1 2
1 3
1 4
2 3
Sample Output 1
1 2
Sample Input 2
22 23
1 2
2 3
3 4
4 5
5 6
5 12
6 7
7 8
8 9
9 10
10 11
11 12
12 22
12 13
13 14
14 15
13 21
15 16
16 17
17 18
18 19
19 20
20 21
Sample Output 2
12 11
Comments
you guys should be aware that problems like this with impossible memory limits or time limits for python is stupid and time wasting, so either if you guys can increase it 128 or no one would solve this in python, this should be changed.
It is made clear on the contest page that not all problems can be solved in Python. Typically, the harder problems of a contest are not tested in Python.
I do not care if no one solves the problem in Python. Just rewrite your solution in C/++ or Rust or Zig or whatever.