DMPG '18 S6 - Mimi and Carrots

View as PDF

Submit solution


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

Problem type

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, ..., 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 \leq N \leq 1\,000
1 \leq M \leq 5\,000

Subtask 2 [80%]

1 \leq N \leq 100\,000
1 \leq M \leq 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

There are no comments at the moment.