WHT - Walk home together

no tags 

A group of f friends get together to have a coding problem-solving party at their university computer lab every weekend. Unfortunately, it closes at 22:00, at which point they have no other option but to walk home. The city they live in can be described as n junctions connected by m bidirectional roads. Since these friends have been interrupted from coding their solutions, each one of them wants to get home as fast as possible to finish his and submit it. At the same time, they each have a few problems that they want to discuss with the others, so they will pick such a path that the entire group can walk together for as long as possible. On top of that, so that this walk would feel fresh every time, they would like to take a different path each weekend, for as long as possible. 

The group of friends were able to figure out both the length of the longest path they could all efficiently walk together, as well as how many distinct such paths there are - do you think you can do it, too?

Input

The first line contains an integer T - the number of test cases. T test cases follow, each in the given format. Test cases are separated by a blank line.

The first line of a case contains four integers n m c f - the number of junctions, the number of two-way roads connecting the junctions, the junction at which the computer lab is located, and the number of friends. Junctions are numbered from 1 to n.

The second line contains f distinct integers F1  ... Ff - Fi is the junction where friend number i lives. None of them are equal to c.

The following m lines contain three integers x y z, denoting a two-way road connecting junctions x and y, of length z. Each unordered pair x, y will be present at most once.

You can assume that the city is connected.

Output

Output two integers L and W.

A 'path' is a sequence of junctions a1 ... akwhere for all 1 ≤ i < k the junctions ai and ai+1 are connected by a road.

L is the length of the longest path, such that for all 1 ≤ i ≤ f if after walking this path friend number i can get home the soonest at some time L+ti, there exists no path from c to Fi shorter than L+ti. In other words, none of the friends could have gotten home sooner if they would have chosen a different path which did not include the one of length L.

W is the number of such paths, modulo 109+7.

Two paths are considered distinct if either

a) they contain a different number of junctions

or

b) they contain the same number of junctions (lets call that k), where one path is described by a1 ... ak and the other by b1 ... bkand there exists some 1 ≤ i ≤ k such that ai ≠ bi.

Constraints

1  ≤ f < n ≤ 5000

n-1 ≤ m ≤ min(106, n*(n-1)/2 )

1 ≤ c ≤ n

1 ≤ F≤ n

1 ≤ x < y ≤ n

1 ≤ z ≤ 4*105 

1 ≤ T ≤ 500

Additionally, if T > 1, n ≤ 50.

The largest input file is under 16MB.

Example

Input:
3
9 12 2 3
9 8 1
2 5 3
2 3 7
2 4 5
3 6 4
6 7 2
5 7 20
4 7 8
4 8 50
7 9 10
7 8 30
1 8 15
1 9 15

9 12 2 3
9 8 1
2 5 3
2 3 7
2 4 5
3 6 4
6 7 2
5 7 20
4 7 8
4 8 10
7 9 10
7 8 30
1 8 15
1 9 15

9 12 2 3
9 8 1
2 5 3
2 3 7
2 4 5
3 6 4
6 7 2
5 7 20
4 7 8
4 8 10
7 9 10
7 8 30
1 8 4
1 9 4

Output:
13 2
5 1
15 1

Explanation

In the first case, the paths are 2,3,6,7 and 2,4,7. Friends number 1 and 2 can then go straight home, and friend number 3 can go home either through junction 8 or 9. For each friend, this is an optimal path.

In the second case, friend number 1 can get home the fastest the same ways as before, friend number 2 can get home fastest by going 2,4,8 and friend number 3 by going 2,4,8,1. Hence the longest path which all friends are willing to take is 2,4 of length 5, and no other such path exists.

In the third case, the first friend can get home the fastest by 2,3,6,7,9 or 2,4,7,9 or 2,4,8,1,9; the second friend's only fastest path is 2,4,8, and the third friend is only willing to take the path 2,4,8,1. Hence the longest path they are all willing to take has length 15 and it is 2,4,8. 


hide comments
guymmk: 2024-06-03 13:22:05

@eyadooz you didnt even solve it yet

eyadooz: 2024-06-02 19:03:13

too easy basically dijkstra + DAGS with a few tweaks



Last edit: 2024-06-02 19:03:53

Added by:Hodobox
Date:2017-08-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:inspired by CANDN