Có \(N\) thị trấn của hải ly, được đánh số từ \(1\) đến \(N\) theo thứ tự độ cao giảm dần. Không có hai thị trấn nào có cùng độ cao. Có \(M\) con kênh một chiều nối các cặp thị trấn khác nhau. Con kênh thứ \(i\) chảy từ thị trấn \(S_i\) đến thị trấn \(E_i\). Các con kênh đều chảy từ thị trấn cao xuống thị trấn thấp; không thể di chuyển ngược dòng.

Hải ly Bitaro có \(N\) người bạn, mỗi thị trấn có đúng một người bạn sinh sống. Bitaro dự định tổ chức \(Q\) bữa tiệc và mời bạn bè đến dự. Với bữa tiệc thứ \(j\), có \(Y_j\) người bạn bận nên không thể tham dự. Bữa tiệc này được tổ chức tại thị trấn \(T_j\); những người không thể đi từ thị trấn của mình đến \(T_j\) chỉ bằng các con kênh cũng không thể tham dự. Tất cả những người bạn còn lại đều đến dự tiệc.

Mỗi người đến địa điểm tổ chức tiệc bằng các con kênh. Có thể có nhiều đường đi, nhưng vì các bạn của Bitaro rất thích kênh nên họ luôn chọn một đường đi đi qua nhiều con kênh nhất.

Với mỗi bữa tiệc, hãy tính số con kênh mà người đi qua nhiều kênh nhất trong số những người tham dự đã sử dụng. Nếu không có ai tham dự, hãy trả lời \(-1\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa ba số nguyên \(N, M, Q\): số thị trấn, số con kênh và số bữa tiệc.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(S_i, E_i\), mô tả một con kênh một chiều từ \(S_i\) đến \(E_i\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(T_j, Y_j\), sau đó là \(Y_j\) số nguyên \(C_{j,1}, C_{j,2}, \ldots, C_{j,Y_j}\). Bữa tiệc thứ \(j\) được tổ chức tại \(T_j\); những người bạn sống ở các thị trấn \(C_{j,1}, \ldots, C_{j,Y_j}\) đều bận.

Các số trên cùng một dòng được phân cách bằng dấu cách.

Dữ liệu ra

In \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) chứa số con kênh lớn nhất mà một người tham dự bữa tiệc thứ \(j\) đi qua. Nếu không có ai tham dự bữa tiệc này, in \(-1\).

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(0 \le M \le 200\,000\).
• \(1 \le Q \le 100\,000\).
• \(1 \le S_i < E_i \le N\) với \(1 \le i \le M\).
• \((S_i,E_i) \ne (S_j,E_j)\) với \(1 \le i < j \le M\).
• \(1 \le T_j \le N\) với \(1 \le j \le Q\).
• \(0 \le Y_j \le N\) với \(1 \le j \le Q\).
• \(1 \le C_{j,1} < C_{j,2} < \cdots < C_{j,Y_j} \le N\) với \(1 \le j \le Q\).
• \(Y_1+Y_2+\cdots+Y_Q \le 100\,000\).

Phân nhóm

1. \(7\) điểm: \(N \le 1000\), \(M \le 2000\), \(Q=1\).
2. \(7\) điểm: \(Q=1\).
3. \(86\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

1
3
0

12 17 10
1 2
2 3
3 4
1 5
2 6
3 7
4 8
5 6
6 7
7 8
5 9
6 10
7 11
8 12
9 10
10 11
11 12
6 3 1 7 12
3 7 1 2 3 4 5 6 7
11 3 1 3 5
9 2 1 9
8 4 1 2 3 4
1 1 1
12 0
10 3 1 6 10
11 8 2 3 5 6 7 9 10 11
8 7 2 3 4 5 6 7 8

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

Nguồn

JOI 2018, trại huấn luyện mùa xuân, ngày thi 3: Bitaro's Party.