ADATRIP - Ada and Trip


Ada the Ladybug loves trips. She travels around world taking photos and souvenirs. This week she went to Buganda. Common Tourist would surely travel around main city and some conurbations, but Ada has different politics. She wants to go as far as possible (because photos from outlying places are much more valuable).

Problem is, that Buganda is very large so she can barely guess such places. Luckily, you are around so she asked you for help. Can you tell her, how far and how many cities are most distant (if the shortest path is used)?

Input

The first line will contain three integers 1 ≤ N ≤ 5*105, 0 ≤ M ≤ 106, Q, the number of cities in Buganda, the number of roads and number of queries (possible arrival cities).

Then M lines follow, with three integers 0 ≤ A, B < N, 0 ≤ L ≤ 10, A, B are cities, which the (bidirectional) road connets and L is length of the road.

Afterward, Q lines follow, each with number 0 ≤ qi < N, meaning the city of arival.

You are asured that max(N,M)*Q will be always lesser/equal than 107

Gentle warning: Since we are in real world and not in some "graph theory", multiedges and self-edges are completely valid!

Output

For each query print two numbers: The distance of most distant place(s) and number of such places.

Example Input

10 10 10
1 1 1
1 2 1
1 2 3 
3 1 1
5 4 10
8 5 10
5 6 5
6 7 3
6 9 3
9 7 4
0
1
2
3
4
5
6
7
8
9

Example Output

0 1
1 2
2 1
2 1
20 1
10 2
15 2
18 2
20 1
18 2

Most distant cities (explanation)

0
2 3
3
2
8
4 8
4 8
4 8
4
4 8

hide comments
ashish_2495: 2020-05-26 18:32:54

EVERYTHING OF MINE IS CORRECT INSTEAD IT IS GIVING WA IN RUNNING 15TH TEST CASE
I AM USING BFS

Last edit: 2020-05-26 18:33:22
binario: 2020-05-24 16:16:22

If you are given TLE and you is using set/map, try a implementation without it. The constant of the redBlackTree is very high and the time limit for this problem is very tight.

s_piyush: 2020-05-18 18:03:51

normal dijkstra works!

thewatch: 2020-04-24 12:51:46

getting TLE on the 15th test case while using normal Dijkstra.

chiri4: 2020-04-07 04:23:32

How many cases are there ? Should we read input until empty line or something ? I am getting error reading the input in the 15 case. Any clue ? I am using Java
After many changes I am reading it as while (in.hasNextLine()), but still fails. However, it pass in ideone. Please, help

Last edit: 2020-04-07 04:28:08
kkmeliodus: 2019-08-01 15:22:46

Use optimised dijikstras for small weight otherwise you will get TLE with normal Dijikstras otherwise they would not have given such constraints. Link for approach is http://www.geeksforgeeks.org/dials-algorithm-optimized-dijkstra-for-small-range-weights/

ebraheemahmed: 2018-08-13 00:00:37

I'm using Dijkstra and got WA at 15th test cases , why ?!?!?

soham_12345: 2018-07-03 15:03:06

why spfa gives WA?

straw__hat: 2018-05-24 15:17:02

I'm getting tle on 15th test case. Don't know why? :(

sharif ullah: 2018-01-04 17:31:25

easy one....normal dijikstra works! no need optimized dijikstra for small weight,,,,
*** node numbering start from '0 '(mind it) !!!

Last edit: 2018-01-04 17:31:46

Added by:Morass
Date:2017-02-09
Time limit:5.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU