Sample Input 2 không đúng định dạng và đã bị loại bỏ.

Berland là một đất nước có lịch sử rất lâu đời, nơi các con đường được xây dựng rồi lại bị phá bỏ trong suốt nhiều thế kỷ. Biết rằng tại mọi thời điểm luôn tồn tại đúng ~n~ thành phố ở Berland. Bạn có trong tay ~t~ bản ghi về các thời khắc quan trọng của lịch sử, được đánh số từ ~1~ đến ~t~. Mỗi bản ghi mô tả danh sách các con đường hai chiều giữa một số cặp thành phố, tức là những con đường có thể sử dụng để di chuyển ở Berland tại đúng thời điểm lịch sử đó. Bạn vừa phát hiện ra một cỗ máy thời gian có thể đưa bạn qua các thời khắc quan trọng nói trên. Đáng tiếc là bạn không thể tự chọn thời điểm đến, nhưng bạn biết trước thứ tự gồm ~k~ thời điểm ~a_1, a_2, \dots, a_k~ mà cỗ máy sẽ lần lượt đưa bạn tới.

Vì thời gian giữa hai lần dịch chuyển là rất ngắn, nên mỗi khi tới một thời điểm mới (kể cả sau lần dịch chuyển cuối cùng), bạn chỉ có thể đi qua nhiều nhất một con đường đang tồn tại tại thời điểm đó, và con đường này phải xuất phát từ thành phố mà bạn đang đứng ngay trước khi dịch chuyển.

Ban đầu, bạn đang ở thành phố ~1~, và cỗ máy đã đưa bạn tới thời điểm ~a_1~. Mục tiêu là đến thành phố ~n~ càng sớm càng tốt.

Yêu cầu: Hãy xác định số lần du hành thời gian nhỏ nhất cần thực hiện để đi từ thành phố ~1~ đến thành phố ~n~. Lưu ý rằng lần dịch chuyển tới thời điểm ~a_1~ cũng được tính là một lần du hành.

Input

• Dòng đầu chứa hai số nguyên ~n~ và ~t~ ~(2 \le n \le 2 \cdot 10^5, 1 \le t \le 2 \cdot 10^5)~ - số thành phố và số bản ghi về các thời khắc lịch sử.

• Sau đó là mô tả của ~t~ bản ghi.

Với mỗi bản ghi ~i~:

• Dòng đầu chứa số nguyên ~m_i~ ~(0 \le m_i \le \min(n \cdot \frac{n - 1}{2}, 2 \cdot 10^5))~ - số con đường trong bản ghi thứ ~i~.

• Mỗi trong ~m_i~ dòng tiếp theo chứa hai số nguyên ~v_j~, ~u_j~ ~(1 \le v_j, u_j \le n, v_j \ne u_j)~ - hai thành phố được nối với nhau bởi một con đường hai chiều tại thời điểm ~i~.

Sau phần mô tả các bản ghi:

• Một dòng chứa số nguyên ~k~ ~(1 \le k \le 2 \cdot 10^5)~ - số lần dịch chuyển/thời điểm xuất hiện trong hành trình.

• Một dòng chứa ~k~ số nguyên ~a_1, a_2, \dots, a_k~ ~(1 \le a_i \le t)~ - thời điểm mà bạn đứng tại sau mỗi lần dịch chuyển.

Ràng buộc bổ sung:

• Tổng tất cả các giá trị ~m_i~ không vượt quá ~2 \cdot 10^5~.

• Với mỗi bản ghi, cùng một cặp thành phố vô hướng không xuất hiện lặp lại trong mô tả các con đường của bản ghi đó.

Output

In ra một số nguyên duy nhất:

• Số lần du hành thời gian nhỏ nhất để đi từ thành phố ~1~ tới thành phố ~n~;

• Hoặc ~-1~ nếu không thể thực hiện được.

Scoring

Sample Input 1

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

Sample Output 1

5

Notes

• Sau lần dịch chuyển thứ ~1~, bạn ở thời điểm ~2~, nhưng từ thành phố ~1~ không có cạnh phù hợp nên chưa đi đâu được.

• Sau lần dịch chuyển thứ ~2~ tới thời điểm ~1~, bạn đi từ ~1~ sang ~2~.

• Sau lần dịch chuyển thứ ~3~ tới thời điểm ~2~, bạn đi từ ~2~ sang ~3~.

• Sau lần dịch chuyển thứ ~4~ tới thời điểm ~1~, bạn buộc phải đứng yên.

• Sau lần dịch chuyển thứ ~5~ tới thời điểm ~2~, bạn đi từ ~3~ sang ~5~ và hoàn thành.