字符串启蒙

描述

字符串决定出一道比较简单的小姜作为启蒙。

这里有两个字符串的集合$S$和$T$(以trie树的形式给出,大小分别为$n+1$,$m+1$)。令$S$中的字符串分别为$s_0, s_1, s_2 \dots s_n$, $T$中的字符串分别为$t_0, t_1, t_2 \dots t_m$($s_0, t_0$都是空串)。

对于形如$s_i, t_j$的一对字符串，定义$s_i+t_j$为将$s_i$和$t_j$拼接得到的字符串。求$\{s_i+t_j | 0 \leq i \leq n, 0 \leq j \leq m\}$中有多少个本质不同的字符串。

两个字符串本质不同当且仅当：它们的长度不同或某一个位置上对应的字符不同。

输入数据

第1行输入为$n$和$m(1 \leq n, m \leq 1e6)$，代表$S$和$T$中分别有多少个非空的字符串。

接下来$n$行输入，每行表示$S$中的一个字符串，第$i$行的输入为一个整数和一个字符: $pre, ch$。($0 \leq pre < i$, ch 是小写字符)，表示$s_i = s_{pre} + ch$。

接下来$m$行输入，每行表示$T$中的一个字符串，第$j$行的输入为一个整数和一个字符: $pre, ch$。($0 \leq pre < i$, ch 是小写字符)，表示$s_i = s_{pre} + ch$。

输出数据

输出一个整数，表示能拼接出的本质不同字符串的数量。

样例输入1

3 2
0 a
1 b
2 a
0 a
1 a

样例输出1

8

样例解释1

能被拼接出的字符串分别是：$\phi, a, aa, aaa, ab, aba, abaa, abaaa$

样例输入2

5 5
0 a
1 a
2 a
1 b
4 a
0 b
0 a
1 a
1 b
4 a

样例输出

28