By the year 3018, Summer Informatics School had greatly grown. Hotel «Berendeetronik» had been chosen as a location of the school. The camp consists of
Everything was perfect until the rain started. The weather forecast promises that the rain will continue for
Unfortunately, despite all the efforts of teachers, even in the year 3018 not all the students are in their houses by midnight. As by midnight all students have to go to bed, it is important to find the maximum travel time between all pairs of houses for each day, so every student knows the time when he has to run to his house.
Find the maximal travel times of the paths between any pair of houses after
In the first line you are given two integers
In the next
It is guaranteed that every two houses are connected by a sequence of pathways.
Print
Subtask # | Score | Constraints |
---|---|---|
1 | 11 | |
2 | 12 | |
3 | 14 | All |
4 | 31 | |
5 | 32 | No additional constraints |
Sample Input 1 | Sample Output 1 |
5 10
|
200 200 200 210 220 230 260 290 320 350
|
In the first three days
In the third day
In the sixth day
Subtask | Score |
---|---|
1 | 11 |
2 | 12 |
3 | 14 |
4 | 31 |
5 | 32 |
6 | 0 |