Encrypted Message

All submissions for this problem are available.
Recently little Chef was challenged by little Devu. Devu asked little Chef to encrypt a given message efficiently which he will send to Churu. Can you help little Chef in doing so ? Problem can be stated formally as follows.
Devu gave little Chef a tree containing N nodes. Each node of the tree contains an lowercase English alphabet (a  z). He also gave a set S of M strings.
Using the set S and the given tree, Chef need to construct another set S1 of size M. To construct the set S1 he does the following
 For each element from the set S, a string e_{i}, he finds the most similar string a_{i} which is present in the given tree. Then he inserts a_{i} (may be null string) into the new set S1. Note that sets S and S1 may contain duplicate elements.
 Most similar string a of a string e is defined as the longest length substring of string e which is present in the tree. If there are multiple such substrings, then the one whose starting index is smallest is taken. Example, e = 'abc' and suppose 'a', 'ab' and 'bc' are present in the tree, then we take 'ab' (not 'bc').
 We say a string a is present in the tree if there exist two nodes n1 and n2 (not necessarily distinct) such that the the string represented by the path going from n1 to n2 is same as a.
 String represented by the path between nodes n1 and n2 is string obtained when we concatenate the characters available at the nodes in the path between n1 and n2.
Outcome of the encryption is also a string str such that all elements of set S1 are present in str as a substring. If there are many such str then the one with smallest length is chosen. If there are still many such str then the one which is lexicographically smallest is chosen. You need to print the encrypted string str. If str is null string then print "1" without quotes.
Input
 The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains two space separated integers N and M as described in the problem statement. N represents the size of the tree. M represents the size of the set S.
 Next line contains N space separated characters ('a' to 'z'). i^{th} character represents the character available at the i^{th} node.
 Next N1 lines each contains two space separated integers u and v denoting there is edge between node u and v.
 Next M lines each contains a string e_{i}. These M strings are the elements of the set S.
Output
In T lines, for each test case output the answer in a new line. Answer to a testcase is the final encrypted message as described in the problem statement.
Constraints
 1 ≤ T, M ≤ 10
 1 ≤ N ≤ 1000
 1 ≤ u, v (u != v) ≤ N
 Say maximum degree of a node among all the nodes of the tree be maxDeg.
 If (maxDeg <= 2) :
 1 ≤ Sum of length of strings of set S ≤ 10010
 Else :
 1 ≤ Sum of length of strings of set S ≤ 3010
Example
Input: 2 4 4 b a b c 1 2 2 3 2 4 ac dbab af g 4 3 b a b c 1 2 2 3 2 4 pq rst uvwz Output: acbab 1
Author:  triveni 
Tags  triveni 
Date Added:  10032015 
Time Limit:  2.5 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 