PION Suffix Automata

In the PION operating system, the folder structure is very different from that in Windows. In Windows, folders form a rooted tree with parent-child relationships. In the PION system, however, there is no parent-child relation; instead, the folders form an unrooted tree with n folders and n-1 bidirectional connections, ensuring that every folder is accessible from every other folder.

Each folder can store files. Like in Windows, each file name contains an extension (for example, read.me or code.cpp). To ease file operations based on file extensions, the interactive program dmc (also called the PION Suffix Automata) supports the following three operations:

1. Distance Query: Given two folders u and v, determine the distance between them. The distance is defined as the minimum number of direct accesses (edges) needed to move from one folder to the other. For example, the distance from a folder to itself is 0, and if two folders are directly connected, their distance is 1.

   query /p u v
       

2. Extension Count Query: Given two folders u and v and a file extension specification of the form *.A (where A is a lowercase string), count the total number of files with extension A that are present in all folders on the path from u to v (inclusive). The folder path is the unique path between two nodes in the tree.

   query /e u v *.A
       

3. Extension Delete Operation: Given two folders u and v and a file extension specification of the form *.A, delete all files with extension A in every folder on the unique path between u and v (inclusive) and output the number of files deleted.

   del /e u v *.A
       

Input/Output Format:

The system first describes the folder structure and the initial files in each folder, followed by a series of operations to perform. Specifically, the input format is as follows:

• The first line contains two integers n and m, denoting the number of folders and the number of operations, respectively.
• The next n-1 lines each contain two integers u and v, indicating that there is a direct connection between folder u and folder v.
• The following n lines describe the files in each folder (from folder 1 to folder n). Each line begins with an integer k, the number of files in that folder, followed by k file names. Each file name is in the format name.extension.
• The next m lines each contain an operation command as described above.

For each operation, output the result on a separate line. For distance and count queries, print the computed integer. For delete operations, print the number of files deleted.

Note: In any file name, the extension is the substring that follows the last period (.). You should use LaTeX formatting for any formulas. For example, the number of folders and connections satisfy \(n\) and \(n-1\) respectively.

inputFormat

The input begins with two space-separated integers \(n\) and \(m\) \( (1 \leq n, m \leq 10^5) \). The next \(n-1\) lines each contain two integers \(u\) and \(v\), indicating a bidirectional connection between folders \(u\) and \(v\).

Then follow \(n\) lines. The \(i\)-th of these lines describes folder \(i\) and begins with an integer \(k\) (the number of files), followed by \(k\) strings representing the file names.

Finally, the next \(m\) lines each describe an operation in one of the following forms:

query /p u v
query /e u v *.A
 del /e u v *.A

Here, \(u\) and \(v\) are folder indices, and in *.A, A is a lowercase string representing the file extension.

outputFormat

For each operation, output the result on a new line. For the distance query (query /p), output the distance (number of edges) between the two folders. For the extension count query (query /e), output the total count of files ending with the specified extension on the path. For the delete operation (del /e), output the number of files that were deleted.

sample

5 5
1 2
2 3
2 4
1 5
2 read.me code.cpp
1 doc.txt
2 a.txt b.cpp
1 test.txt
1 hello.txt
query /p 3 4
query /e 3 5 *.txt
del /e 2 4 *.txt
query /e 2 4 *.txt
query /p 5 4

2
3
2
0
3

</p>