After completing her final semester, Savita is back home. She is excited to meet all her friends. Her N friends live in different houses spread across the city.

There are M roads connecting the houses. The road network formed is connected and does not contain self loops and multiple roads between same pair of houses. Savita and Friends decide to meet.

Savita wants to choose a point(not necessarily an integer) P on the road numbered K , such that, the maximum of dist(i) for all 1≤i≤N is minimised,

wheredist(i) is the shortest distance between the i 'th friend and P .

where

If K 'th road connects friend A and friend B you should print distance of chosen point from A . Also, print the max(dist(i)) for all 1≤i≤N . If there is more than one solution, print the one in which the point P is closest to A .

Note:

- Use scanf/printf instead of cin/cout. Large input files.
- Order of
A andB as given in the input must be maintained. If P is at a distance of 8 fromA and 2 fromB , you should print 8 and not 2.

**Input Format**

First line contain

T testcases follow.

First Line of each testcase contains 3 space separated integers

Next

**Output Format**

For each testcase, print two space separated values in one line. The first value is the distance of

**Constraints**

**Sample Input**

```
2
2 1 1
1 2 10
4 4 1
1 2 10
2 3 10
3 4 1
4 1 5
```

**Sample Output**

```
5.00000 5.00000
2.00000 8.00000
```

**Explanation**

First testcase:

AsK = 1, they will meet at the point P on the road that connects friend 1 with friend 2 . If we choose mid point then distance for both of them will be 5 . In any other position the maximum of distance will be more than 5 .

As

Second testcase:

AsK = 1, they will meet at a point P on the road connecting friend 1 and friend 2 . If we choose point at a distance of 2 from friend 1 : Friend 1 will have to travel distance 2 .

Friend2 will have to travel distance 8 .

Friend3 will have to travel distance 8 .

Friend4 will have to travel distance 7 .

So, the maximum will be8 .

In any other position of point choosen, the maximum distance will be more than8 .

As

Friend

Friend

Friend

So, the maximum will be

In any other position of point choosen, the maximum distance will be more than

이 문제에 대한 솔루션을 작성했습니다.

ReplyDeletehttp://blog.myungwoo.kr/52