在遙遠的魔法王國裡，有一棵古老的智慧之樹，名為「知識之樹」。樹上每個節點都刻有一個神秘數字，象徵不同的魔法符文力量。傳說，樹上隱藏著多把魔法金鑰，只有按照正確的魔法序列才能開啟王國最神秘的寶藏。

樹共有 $n$ 個節點，節點編號為 $1$ 到 $n$，每個節點 $i$ 上的數字為 $val_i$。王國派出 $p$ 位魔法守衛，他們各自站在樹上的某個節點，第 $i$ 位守衛持有的金鑰位於節點 $id_i$，不會有兩位守衛站在同個節點上。

樹由 $n - 1$ 條邊所組成，第 $i$ 條邊連接兩個節點 $u_i,\ v_i$，使整棵樹保持連通，並且保證對於所有節點的子節點的 $val_i$ 皆不相同。

每把金鑰對應一條金鑰序列，即從根節點 $1$ 到金鑰所在節點沿途經過節點的數字組成的序列。例如，如果金鑰位於節點 $5$，根節點到該節點經過 $1 \rightarrow 2 \rightarrow 5$，對應金鑰序列為 $[val_1, val_2, val_5]$。

王國法典規定：
1. 將所有金鑰序列按照字典序排列。
2. 第 $k$ 小的金鑰序列就是打開寶藏的密碼序列。

請你輸出這組密碼序列。

以 $5$ 個節點，以下樣子的樹為例：

若 $val = [7,\ 4,\ 2,\ 5,\ 10]$ 且有 $3$ 位守衛分別站在編號 $1,\ 4,\ 5$ 的節點上。
第一位守衛的金鑰序列為 $[7]$，
第二位守衛的金鑰序列為 $[7,\ 5]$，
第三位守衛的金鑰序列為 $[7,\ 10]$，
按照字典序由小到大排，第一小的是第一位守衛的金鑰序列，第二小的是第二位守衛的金鑰序列，第三小的是第三位守衛的金鑰序列，
所以若 $k = 2$，則密碼序列為 $[7,\ 5]$。

字典序定義：
給定兩個序列 $A = [a_1, a_2, \dots, a_p]$ 與 $B = [b_1, b_2, \dots, b_q]$，序列 $A$ 小於 $B$（記作 $A < B$），如果存在最小的索引 $i$，使得 $a_i \ne b_i$，且 $a_i < b_i$。
如果一個序列是另一個序列的前綴，則較短的序列視為較小。例如 $[1,2] < [1,2,3]$。

對於所有測試資料：
$1 \le p \le n \le 10$^$6$
$1 \le k \le p$
$1 \le u_i,\ v_i \le n$
$1 \le id_i \le n$
$1 \le val_i \le 10$^$9$
保證根節點為 $1$，且對於所有節點的子節點的 $val_i$ 皆不相同。
保證所有 $id_i$ 皆不相同。

評分說明：
每筆測試資料執行時間限制為 7 秒，依正確通過測資筆數給分，其中：
第 1 子題組 30 分：$n \le 100$。
第 2 子題組 70 分：無額外限制。