Maximizing Pattern Occurrences in a Spacetime Journey

You are given a connected tree of spacetime nodes with n nodes and n-1 edges. Each node i has a scenery value ai. The tree is connected by spacetime channels (edges) such that you can travel between nodes. You start at node 1 and may travel along the channels. Because of the special nature of spacetime travel, each spacetime channel can be used at most once. In other words, the only valid journeys are simple paths starting from node 1 (note that repeating an edge would mean using it twice).

As you travel, you record the scenery values of the nodes you visit in order, forming a recreated scenery sequence. For any given sequence A and another sequence B, we define the occurrence count of A in B as the maximum number of contiguous and non‐overlapping parts into which you can partition B such that A appears as a substring in each part. (Recall that a substring is any consecutive segment of a sequence.)

You are given q queries. In the i-th query, you are given a lingering scenery sequence si of length mi. For each query, your task is to choose a valid journey (i.e. a simple path starting from node 1) so that when you partition its recreated scenery into as many contiguous parts as possible with each part containing si as a substring, the number of parts is maximized. Output that maximum occurrence count.

Note:

• Each query is independent; the journey for one query does not affect another.
• A contiguous subsequence of consecutive numbers in any sequence is called a substring of that sequence.
• If a formula is displayed, it is formatted in \(\LaTeX\) (for example, \(n\) and \(a_i\)).

Input Format: The first line contains two integers n and q — the number of nodes and the number of queries. The second line contains n integers a1, a2, \dots, an representing the scenery at each node. Then follow n-1 lines, each containing two integers u and v, which indicate there is a spacetime channel connecting nodes u and v. After that, q queries follow. For each query, the first integer is m — the length of the lingering scenery sequence, followed by m integers representing the sequence s.

Output Format: For each query, print a single integer — the maximum occurrence count of the query sequence in any valid recreated scenery sequence.

inputFormat

The input begins with two integers n and q on one line, separated by a space.

The second line contains n space‐separated integers representing a1, a2, …, an.

The following n-1 lines each contain two integers u and v representing an edge between nodes u and v.

Then, there are q queries. Each query consists of a line starting with an integer m followed by m space‐separated integers representing the query sequence s.

outputFormat

For each query, output one integer on a separate line denoting the maximum occurrence count of the query sequence in any valid journey’s recreated scenery.

sample

5 2
1 2 3 2 1
1 2
2 3
2 4
1 5
2 1 2
3 1 2 3

1
1