题目描述

有一棵 $n$ 个节点的大树，上面每条边有一个小写字符。

对于任意两个不同的点 $u,v$，我们可以在树上找到 $u$ 出发到 $v$ 终止的唯一的一条最短路径，并将沿途经过的边上的字符依次写下来，得到一个字符串。

对于一个字符串，如果存在这样一个点对 $(u,v)$，使得它们路径上的字符串与其完全匹配，那么我们就称这个字符串属于这棵树。

现在有m个迷失的字符串，请你写一个程序帮助判断每一条字符串是否属于这棵树。

输入格式

第一行包含一个正整数 $n(2\le n\le 30000)$，表示树的点数。

接下来 $n-1$ 行每行包含两个正整数 $a,b$ 和一个小写字符 $c(1\le a,b\le n,a\neq b)$，表示 $a$ 点到 $b$ 点之间有一条无向的树边，上面写着字符 $c$。

接下来一行包含一个正整数 $m(1\le m\le 30000)$，表示迷失的字符串的个数。

接下来 $m$ 行，每行一个由小写字符组成的字符串，分别表示每个迷失的字符串。

输入数据保证所有迷之的字符串的长度之和不超过 $30000$。

输出格式

包含 $m$ 行，对于第 $i$ 行，如果在树上可以找到第 $i$ 个字符串，输出 YES，否则输出 NO。

4
1 2 b
1 4 a
2 3 c
9
bc
cb
b
c
d
aa
ab
abc
cba

YES
YES
YES
YES
NO
NO
YES
YES
YES