题目背景

NOIP2018原创模拟题T6

NOIP2018原创模拟赛DAY2 T3

NOIP DAY1 T3+ or DAY2 T3 难度

鉴于 NOIP2017 DAY2 T3 的难度，就有了这道题。然而这道题考察的知识并不是后缀自动机

题目描述

小P是一个技术高超的程序员，他开发了一套自己的操作系统，称为PION系统，该系统与Windows和Linux有很大不同，目前他正在测试该系统。

PION系统与Windows系统最大的不同在于文件的储存与操作，POIN的文件夹没有父子之分。我们知道，在Windows系统中，可以在文件夹里新建子文件夹。但是，PION系统文件夹不分父子关系，但是部分文件夹之间可以互相直接访问，我们称这种关系为互访关系，而且，对于一个有$n$个文件夹的系统来说，这种互访关系有$n-1$个，且保证所有文件夹均可以通过互访关系而互相访问。也就是说：我们可以把Windows中的文件夹的集合看作一棵有根树，而把PION系统中的文件夹集合看作为无根树。

在PION系统中，每个文件夹都可以储存文件，和Windows一样，文件名包含后缀名。

现在小P正在构思一种可以对文件夹中文件后缀进行方便操作的交互式程序dmc，他也将其称为PION后缀自动机。由于他太忙了，所以他希望你帮他实现部分功能。

他希望你帮他实现三个功能：

1.计算两个文件夹之间的距离。我们定义：文件夹之间的距离为其中一个文件夹通过互访达到另一个文件夹最少互访次数。比如：同一个文件夹距离为0，两个有互访关系的文件夹距离为1。

2.计算两个文件夹路径之间（包含这两个文件夹）的文件夹中的文件的后缀名为A的文件数量，其中A是一个小写字符串。提示：我们可以把PION文件夹之间的路径理解为树中两节点之间的路径。

3.删除两个文件夹路径之间（包含这两个文件夹）的文件夹中的文件的后缀名为A的文件，并统计被删除文件的数量。

由于dmc是一个交互系统，所以我们用tab语言描述这三个操作：

query /p u v

表示操作一，其中 u,v 表示两文件夹的编号

query /e u v *.A

表示操作二，其中 u,v 表示两文件夹的编号，$'*'$ 为通配符，$'.'$用于分隔文件名与后缀，A是一个小写字符串。

del /e u v *.A

表示操作三， $u,v, *.A$ 意义与操作二相同。

如果没有看懂题目请结合样例及样例解释来理解。

最后，这个困难的任务就交给你了。

输入格式

第一行两个数，$n,m$，$n$表示文件夹的数量（文件夹编号在$[1,n]$），$m$表示操作的数量

接下来 $n-1$ 行，每行两个数 $u,v$，表示文件夹 $u,v$ 之间有互访关系

接下来 $n$ 行，第$i$行第一个数为 $k$，表示第$i$个文件夹有$k$个文件，接下来为$k$个字符串，表示每个文件的后缀名

再接下来$m$行，每行一串指令，格式见上文

输出格式

对于每个指令，输出一个数，输出数的意义见上文

5 5
1 2
2 4
2 5
1 3
2 cpp c
3 pas txt txt
2 vbs bat
3 vbs cpp pas
4 cpp c pas txt
query /e 1 5 *.txt
query /p 1 4
del /e 2 2 *.txt
query /e 1 5 *.txt
query /e 4 3 *.vbs

3
2
2
1
2

12 7
1 2
1 3
1 4
2 5
2 6
3 7
7 12
8 4
8 9
10 9
11 9
0
2 c c
3 zz c c
0
1 gif
2 png bmp
3 avl avl mpshi
0
4 cpp c pas js
5 a b c d e
0
3 a b c
query /p 11 12
query /e 1 2 *.gif
query /e 6 10 *.c
del /e 2 9 *.c
del /e 3 12 *.c
query /e 5 6 *.gif
query /e 6 1 *.c

7
0
4
3
3
1
0

提示

样例一解释：

如图为样例一大致结构，橙色方框为文件夹，灰色文字表示文件后缀名，红色线条表示文件互访关系。

对于第一个操作：文件夹1到5之间txt文件有3个所以输出3
对于第二个操作：文件夹1与4距离为2
对于第三个操作：删除的为文件夹2的文件，txt文件有两个，所以输出2
对于第四个操作：由于文件夹2的txt文件被删除了，所以1到5之间txt文件只有1个
对于第五个操作：文件夹3到4之间vbs文件有2个所以输出2

数据范围：

30%数据满足：$n,m<=100,k<=3$

50%数据满足：$n,m<=5000,k<=10$

70%数据满足：$n,m<=2 \times 10^4,k<=50$

90%数据满足：$n,m<=5 \times 10^4$

100%数据满足：$n,m<=10^5$，文件总数小于$5 \times 10^5$，文件后缀名为小写字符串且不超过6个字符

其他说明：

1.约50%的数据为完全随机生成

2.数据弱化版：PION后缀自动机（数据弱化版）