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 
cities, numbered 
, with 
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 
such that blockading , or disconnecting all the roads to , will break the Land of the Carrots into at least 
disjoint graphs, or provinces (including ). Among these provinces, the resistance 
Mimi will encounter is the maximum size of any one province. Mimi wants to find city 
such that blockading it will minimize , 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%]
Subtask 2 [80%]
Input Specification
The first line of input will contain 2 integers, and , separated by a space.
The next lines will each contain 2 integers 
and 
, which means there exists a bidirectional road between cities and .
Output Specification
2 integers separated by a space, and . 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
Copy
4 4
1 2
1 3
1 4
2 3
Sample Output 1
Copy
1 2
Sample Input 2
Copy
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
Copy
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.