Là chủ sở hữu đầy tinh thần kinh doanh của một khu nghỉ dưỡng trượt tuyết nổi tiếng thế giới tại Mỹ, bạn muốn tăng doanh số bằng cách cung cấp đồ ăn nhẹ cho các quầy tại những vị trí trọng yếu trên toàn khu đất của mình.

Khu nghỉ dưỡng trượt tuyết được xây trên một ngọn núi. Thang kéo trượt tuyết có thể đưa du khách lên đỉnh núi. Từ đó, họ có thể trượt tuyết đến nhiều địa điểm trên núi.

Trên núi có $n$ khu vực, được đánh nhãn $1..n$. Đỉnh núi là khu vực $1$. Các khu vực được nối bằng những đường trượt chỉ đi xuống dốc. Nói cách khác, sau khi rời một khu vực, không thể quay lại đó nếu không sử dụng thang kéo. Mỗi khu vực (kể cả khu vực $1$) có đúng một quầy đồ ăn nhẹ.

Là chủ khu nghỉ dưỡng, bạn muốn biết cách phân phối đồ ăn nhẹ giữa các quầy hiệu quả đến đâu để phục vụ du khách tốt hơn (và kiếm thêm tiền). Vì vậy, bạn muốn tiến hành một cuộc khảo sát và phân tích kết quả bằng một số truy vấn độc lập. Mỗi du khách tham gia khảo sát có một món ăn nhẹ ưa thích và một danh sách các khu vực ưa thích mà họ muốn ghé thăm. Bạn muốn biết cách tốt nhất để cung cấp món ăn nhẹ ưa thích của họ cho các quầy.

Mỗi truy vấn gồm một tập các khu vực ưa thích của một du khách và một số $k$. Bạn muốn biết có bao nhiêu cách cung cấp món ăn nhẹ ưa thích của du khách này cho đúng $k$ quầy trên núi sao cho các quầy thỏa mãn những điều kiện sau:

1. Với mỗi khu vực ưa thích của du khách này, xét trên tất cả các chuỗi đường trượt đi từ đỉnh núi đến khu vực đó, phải có đúng một quầy bán món ăn nhẹ ưa thích của du khách. (Nói cách khác, họ không được có lựa chọn giữa nhiều hơn một quầy có bán món ăn nhẹ của mình.)
2. Mỗi quầy trong $k$ quầy được cung cấp món ăn nhẹ ưa thích của du khách này phải nằm trên một chuỗi đường trượt nào đó từ đỉnh núi đến một khu vực trong tập truy vấn.

Dữ liệu vào

Mỗi dữ liệu vào gồm một bộ kiểm thử duy nhất. Lưu ý rằng chương trình của bạn có thể được chạy nhiều lần với các dữ liệu vào khác nhau. Dòng đầu tiên chứa ba số nguyên $n$, $m$ và $q$, cách nhau bởi dấu cách, trong đó $n$ ($1\le n\le10^5$) là số khu vực trên núi, $m$ ($1\le m\le n+50$) là số đường trượt và $q$ ($1\le q\le10^5$) là số truy vấn.

Mỗi dòng trong $m$ dòng tiếp theo chứa hai số nguyên $x$ và $y$ ($1\le x,y\le n$, $x\ne y$). Dòng này biểu thị một đường trượt từ khu vực $x$ đến khu vực $y$. Giữa hai khu vực bất kỳ có nhiều nhất một đường trượt. Có thể đến mọi khu vực từ khu vực $1$ bằng một chuỗi đường trượt nào đó.

Mỗi dòng trong $q$ dòng tiếp theo là một dãy số nguyên cách nhau bởi dấu cách, bắt đầu bằng $k$ và $a$, sau đó là $a$ số nguyên $i$. Ở đây, $k$ ($1\le k\le4$) là số quầy cần cung cấp món ăn nhẹ ưa thích của du khách này, $a$ ($1\le a\le n$) là số khu vực trong tập truy vấn, và $a$ số nguyên $i$ ($1\le i\le n$) là nhãn các khu vực trong tập truy vấn. Trong mỗi truy vấn, không có số nguyên $i$ nào lặp lại.

Tổng tất cả các giá trị $a$ của mọi truy vấn không vượt quá $100\,000$.

Dữ liệu ra

In ra $q$ số nguyên, mỗi số trên một dòng riêng, không có dòng trống xen giữa. Chúng biểu thị số cách chọn các quầy để cung cấp đồ ăn cho từng truy vấn, theo thứ tự xuất hiện trong dữ liệu vào. Hai cách được coi là khác nhau nếu có một khu vực được chọn trong cách này nhưng không được chọn trong cách kia.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2
0
2
1

Dữ liệu vào 2

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

Dữ liệu ra 2

0
0
3
2

Dữ liệu vào 3

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

Dữ liệu ra 3

2
0
3
2