Mô tả

Cho một đồ thị vô hướng gồm ~n~ đỉnh. Có ~m~ cạnh xuất hiện lần lượt theo thời gian; cạnh thứ ~i~ xuất hiện tại thời điểm ~i~.

Có ~Q~ truy vấn. Truy vấn thứ ~i~ được mô tả bởi một tập đỉnh ~S_i~.

Tại một thời điểm ~t~, xét đồ thị gồm ~t~ cạnh đầu tiên. Với truy vấn ~S_i~, lấy hợp của tất cả các thành phần liên thông có chứa ít nhất một đỉnh thuộc ~S_i~.

Hãy tìm thời điểm sớm nhất mà đồ thị thu được không còn là đồ thị hai phía.

Nếu không tồn tại thời điểm như vậy, in ra -1.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương ~n, m~ (~1 \le n,m \le 10^5~).
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i, v_i~ (~1 \le u_i,v_i \le n~), mô tả cạnh nối hai đỉnh ~u_i~ và ~v_i~ xuất hiện tại thời điểm ~i~.
• Dòng tiếp theo chứa số nguyên dương ~Q~ (~Q \le 10^5~).
• ~Q~ dòng cuối, mỗi dòng mô tả một truy vấn:
  • Số đầu tiên là ~k~, số lượng đỉnh của tập ~S_i~.
  • Tiếp theo là ~k~ số nguyên, là các đỉnh thuộc tập ~S_i~.

Dữ liệu ra

In ra ~Q~ dòng.

Dòng thứ ~i~ chứa thời điểm sớm nhất mà hợp các thành phần liên thông chứa ít nhất một đỉnh thuộc ~S_i~ không còn là đồ thị hai phía.

Nếu không tồn tại thời điểm như vậy, in ra -1.

Giới hạn

• ~1 \le n,m \le 10^5~.
• ~Q \le 10^5~.
• Tổng số lượng phần tử của tất cả các tập ~S_i~ không vượt quá ~2 \times 10^5~.

Ví dụ

Input

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

Output

3
3
6
-1
3