String Tree Prefix Queries

This problem involves a tree with $N$ nodes and $N-1 edges. The nodes are numbered from 1 to $N$ and each edge in the tree has an associated string. Since the structure is a tree (i.e. a connected acyclic graph), there exists a unique simple (i.e. shortest) path between any two nodes.

You are given the tree information and then $Q$ queries. Each query consists of a string $S$ and two nodes $U$ and $V$. For each query, you need to determine the number of edges on the unique path between $U$ and $V$ whose associated string has $S$ as its prefix.

Input/Output: See below for input and output format details.

Note on Strings: A string A is said to have string S as a prefix if the first |S| characters of A exactly match S. All comparisons are case-sensitive.

Constraints: The input sizes are assumed to be small enough so that a simple DFS-based approach per query is acceptable.

inputFormat

The first line of input contains two integers $N$ and $Q$, the number of nodes and the number of queries respectively.

Then follow $N-1$ lines, each containing two integers $U$ and $V$ and a non-empty string W that denotes an edge between nodes $U$ and $V$ with associated string W.

Following that, there are $Q$ lines. Each query line contains a non-empty string $S$ and two integers $U$ and $V$, where $S$ is the prefix string and $U$, $V$ are the endpoints of the query path.

outputFormat

For each query, output a single line containing one integer: the number of edges on the unique path between $U$ and $V$ whose associated strings start with the given prefix $S$.

sample

3 2
1 2 abcd
2 3 abc
ab 1 3
abcd 1 2

2
1