Validate BFS order queries on a tree

You are given an undirected tree described by two equal-length arrays u and v (each of length n-1). For every index i, there is an undirected edge between u[i] and v[i]. The tree contains exactly n distinct node labels (labels are arbitrary integers).

You are also given q queries. Each query is an array order of length n containing each node label exactly once (a permutation).

For each query, decide whether order can be the output of a standard BFS traversal on this tree under the following rules:

• The BFS start node is order[0] .
• BFS uses a FIFO queue.
• When a node is dequeued, you may enqueue its unvisited neighbors in any order (i.e., neighbor iteration order is not fixed).
• The BFS output is the dequeue order.

Return a boolean for each query.

Example:

• u = [1, 1, 4] , v = [3, 2, 3] defines edges (1,3), (1,2), (4,3) .
• For order = [1,2,3,4] , the answer is true (one valid BFS enqueues 2 then 3 after visiting 1 ).

Constraints (typical interview setting):

• n can be up to 2e5 .
• q can be large; aim for better than O(q * n^2) .