Recall the definition of a trie:
- A trie of size $$$n$$$ is a rooted tree with $$$n$$$ vertices and $$$(n - 1)$$$ edges, where each edge is marked with a character.
- Each vertex in a trie represents a string. Let $$$s(x)$$$ be the string vertex $$$x$$$ represents.
- The root of the trie represents an empty string. Let vertex $$$u$$$ be the parent of vertex $$$v$$$, and let $$$c$$$ be the character marked on the edge connecting vertex $$$u$$$ and $$$v$$$, we have $$$s(v) = s(u) + c$$$. Here $$$+$$$ indicates string concatenation, not the normal addition operation.
- The string each vertex represents is distinct.
We now present you a rooted tree with $$$(n + 1)$$$ vertices. The vertices are numbered $$$0, 1, \cdots, n$$$ and vertex $$$0$$$ is the root. There are $$$m$$$ key vertices in the tree where vertex $$$k_i$$$ is the $$$i$$$-th key vertex. It's guaranteed that all leaves are key vertices.
Please mark a lower-cased English letter on each edge so that the rooted tree changes into a trie of size $$$(n + 1)$$$. Let's consider the sequence $$$A = \{s(k_1), s(k_2), \cdots, s(k_m)\}$$$ consisting of all strings represented by the key vertices. Let $$$B = \{w_1, w_2, \cdots, w_m\}$$$ be the string sequence formed by sorting all strings in sequence $$$A$$$ from smallest to largest in lexicographic order. Please find a way to mark the edges so that sequence $$$B$$$ is minimized.
We say a string $$$P = p_1p_2\cdots p_x$$$ of length $$$x$$$ is lexicographically smaller than a string $$$Q = q_1q_2\cdots q_y$$$ of length $$$y$$$, if
- $$$x \lt y$$$ and for all $$$1 \le i \le x$$$ we have $$$p_i = q_i$$$, or
- there exists an integer $$$1 \le t \le \min(x, y)$$$ such that for all $$$1 \le i \lt t$$$ we have $$$p_i = q_i$$$, and $$$p_t \lt q_t$$$.
We say a string sequence $$$F = \{f_1, f_2, \cdots, f_m\}$$$ of length $$$m$$$ is smaller than a string sequence $$$G = \{g_1, g_2, \cdots, g_m\}$$$ of length $$$m$$$, if there exists an integer $$$1 \le t \le m$$$ such that for all $$$1 \le i \lt t$$$ we have $$$f_i = g_i$$$, and $$$f_t$$$ is lexicographically smaller than $$$g_t$$$.
There are multiple test cases. The first line of th input contains an integer $$$T$$$ indicating the number of test cases. For each test case:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le m \le n \le 2 \times 10^5$$$) indicating the number of vertices other than the root and the number of key vertices.
The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$0 \le a_i \lt i$$$) where $$$a_i$$$ is the parent of vertex $$$i$$$. It's guaranteed that each vertex has at most $$$26$$$ children.
The third line contains $$$m$$$ integers $$$k_1, k_2, \cdots, k_m$$$ ($$$1 \le k_i \le n$$$) where $$$k_i$$$ is the $$$i$$$-th key vertex. It's guaranteed that all leaves are key vertices, and all key vertices are distinct.
It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$2 \times 10^5$$$.
For each test case output one line containing one answer string $$$c_1c_2\cdots c_n$$$ consisting of lower-cased English letters, where $$$c_i$$$ is the letter marked on the edge between $$$a_i$$$ and $$$i$$$. If there are multiple answers strings so that sequence $$$B$$$ is minimized, output the answer string with the smallest lexicographic order.
25 40 1 1 2 21 4 3 51 101
abaab a
The answer of the first sample test case is shown as follows.
The string represented by vertex $$$1$$$ is "a". The string represented by vertex $$$4$$$ is "aba". The string represented by vertex $$$3$$$ is "aa". The string represented by vertex $$$5$$$ is "abb". So $$$B = \{$$$"a", "aa", "aba", "abb"$$$\}$$$.
