It’s a friendship day! Deepika is keen to wish her friend Jyoti with a special bouquet of flowers which she knows Jyoti loves. This bouquet can only be made with a combination of some special flowers and will be incomplete if even one of the flowers is missing. These flowers are sold in different shops across town, and Deepika plans to visit these shops on her way from her home to Jyoti’s office. Each shop sells only one kind of flower, and Deepika doesn’t want to waste time, so she needs to visit exactly one shop selling each kind of flower before reaching Jyoti’s office. There is a flower shop next to Deepika’s home, and one next to Jyoti’s office, so she plans to visit those two anyways.
Help Deepika by finding the shortest path to collect all the flowers and reach Jyoti’s office, while visiting exactly one shop selling each kind of flower. You can assume that at least one such path always exists.
Input format: Multiple inputs in a single line are always separated by single white spaces. The shops are represented by their names as strings (length >=1), and the flowers are represented with numbers.
The first line of input has an integer n
Next, n lines have input in the following format: s f d x1 x2
where
s is the shop name
f is the flower type available in that shop
x1 x2 etc. are the shop names which are at d distance from s
If there is only one shop at distance d, then only x1 is given if there are multiple shops at the same distance, all such shops are listed out in the same line.
The last line of input will have u and v, where u is the first shop (where Deepika’s house is) and v is the last shop (where Jyoti’s office is).
Output Format: The output contains u, v, and the minimum distance Deepika has to travel to get all the flowers and reach Jyoti’s office.
Sample Input 1:
5
a 3 1 b e
b 2 2 c
c 1 1 d
d 5
e 2
a d
Sample Output 1:
a d 4