## DMPG '18 S6 - Mimi and Carrots

View as PDF

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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?

#### 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

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