Đếm cầu trên đồ thị mở rộng

Một vương quốc cổ đại được xây dựng trên những cây cầu. Cây cầu chính là xương sống của mọi kết nối trong vùng đất này, nối liền các thành phố cổ xưa lại với nhau qua những con đường cây xanh mát. Mỗi cây cầu đóng một vai trò thiết yếu trong việc duy trì sự cân bằng và bền vững của hệ thống giao thông của vương quốc.

Bạn được giao nhiệm vụ giải quyết một vấn đề liên quan đến cây cầu. Vương quốc có một cây bao gồm \(N\) đỉnh, tức là một đồ thị không có chu trình và nối liền tất cả các đỉnh. Cây này có \(M\) truy vấn, và mỗi truy vấn yêu cầu kiểm tra một loạt các cạnh mới có thể được thêm vào cây ban đầu. Nhiệm vụ của bạn là trả lời xem với mỗi truy vấn, nếu thêm các cạnh này vào cây, có bao nhiêu cạnh trong đồ thị mới sẽ trở thành cầu?

Một cạnh được gọi là cầu nếu khi loại bỏ nó, đồ thị trở nên không liên thông.

Hãy lưu ý rằng các truy vấn đều độc lập với nhau, và các cạnh thêm vào chỉ mang tính giả định, không thực sự thêm vào cây.

Input

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(2 \leq N \leq 100\,000\), \(1 \leq M \leq 100\,000\)) --- số lượng đỉnh của cây và số lượng truy vấn.

Dòng thứ hai chứa \(N-1\) số nguyên \(p_2, p_3, \ldots, p_N\) mô tả cấu trúc của cây. Cụ thể, cạnh thứ \(i\) nối đỉnh \(i+1\) với đỉnh \(p_i\).

Tiếp theo là \(M\) dòng, mỗi dòng chứa một truy vấn. Truy vấn thứ \(i\) bao gồm số nguyên đầu tiên \(K_i\) --- số cạnh sẽ thêm vào cây, tiếp theo là \(K_i\) cặp số nguyên \((x_{i,1}, y_{i,1}), (x_{i,2}, y_{i,2}), \dots, (x_{i,K_i}, y_{i,K_i})\). Mỗi cặp \((x_{i,j}, y_{i,j})\) mô tả một cạnh mới được thêm vào cây (\(1 \leq x_{i,j}, y_{i,j} \leq N\)). Tổng của \(K_i\) trong tất cả các truy vấn không vượt quá \(100\,000\).

Output

Với mỗi truy vấn, in ra một số nguyên duy nhất là số lượng cầu trong đồ thị sau khi thêm các cạnh của truy vấn vào cây.

Example

7 8
1 1 2 2 3 3
1 4 5
3 4 5 6 7 3 2
1 5 6
1 1 1
1 3 6
2 4 3 2 7
1 5 1
3 1 2 1 3 1 6

4
0
2
6
5
2
4
3

Scoring

• Subtask 1 (30% số điểm): \(N, M \leq 1000\).
• Subtask 2 (70% số điểm): không giới hạn gì thêm.