(wat.*)

Cho một cây có \(n\) nút, các nút được đánh số từ 1 đến \(n\), nút 1 là nút gốc của cây. Mỗi nút trên cây có giá trị là 1 chữ cái tiếng anh in thường. Có \(q\) truy vấn, mỗi truy vấn dạng:

\(x\ s\): trong đó \(x\) là gốc cây con và \(s\) là một xâu.

Với mỗi truy vấn, gọi \(t\) là xâu được xây dựng bằng cách lấy tất cả các ký tự trong cây con gốc \(x\), mỗi nút được lấy chính xác 1 lần. Yêu cầu tính số lượng ký tự nhỏ nhất thêm vào xâu \(t\) để từ \(t\) xây dựng được xâu \(s\).

Dữ liệu vào:

+ Dòng đầu tiên ghi 2 số nguyên \(n,\ q\).

+ Dòng thứ 2 ghi \(n\) ký tự chữ cái in thường, trong đó ký tự thứ \(i(i = 1\ldots n)\) là giá trị của nút thứ \(i\) trên cây, các chữ cái cách nhau 1 dấu cách.

+ \(n - 1\) dòng tiếp theo, mỗi dòng ghi 2 số nguyên \(x,\ y\) cho biết một cạnh trên cây.

+ Tiếp theo là \(q\) dòng, mỗi dòng là 1 truy vấn dạng \(u,\ s\).

Kết quả: ghi trên \(q\) dòng, mỗi dòng một số nguyên là câu trả lời cho truy vấn tương ứng trong input.

Giới hạn:

+ \(2 \leq n \leq 10^{5}\)

+ \(1 \leq q \leq 10^{5}\)

+ \(1 \leq u,\ v \leq n;u
eq v\)

+ \(1 \leq x \leq n\)

Tổng độ dài của các xâu trong truy vấn không vượt quá \(10^{6}\)

Ví dụ: