Trong một thiên hà rất xa, phương thức vận chuyển nhanh nhất là sử dụng siêu ống. Mỗi hypertube kết nối trực tiếp ~K~ trạm với nhau. Hỏi chúng ta phải đi qua bao nhiêu ga để đi từ ga ~1~ đến ga ~N~?

Input

• Dòng đầu tiên của đầu vào chứa ba số nguyên dương: ~N~ ~(1 \le N \le 100 000)~, số lượng trạm ~K~ ~(1 \le K \le 1 000)~, số lượng trạm mà bất kỳ siêu ống đơn nào kết nối trực tiếp với nhau và ~M~ ~(1 \le M \le 1 000)~, số lượng siêu ống.
• Mỗi ~M~ dòng tiếp theo chứa mô tả của một siêu ống đơn: ~K~ số nguyên dương, nhãn của các trạm được kết nối với siêu ống đó.

Output

• Dòng đầu ra đầu tiên và duy nhất phải chứa số lượng trạm tối thiểu được yêu cầu. Nếu không thể di chuyển từ trạm ~1~ đến trạm ~N~, ghi ~-1~.

Sample Input 1

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

Sample Output 1

4

Sample Input 2

15 8 4
11 12 8 14 13 6 10 7
1 5 8 12 13 6 2 4
10 15 4 5 9 8 14 12
11 12 14 3 5 6 1 13

Sample Output 2

3

Làm rõ ví dụ đầu tiên:

• Có thể đi từ trạm ~1~ đến trạm ~9~ chỉ bằng bốn trạm theo các cách sau: ~1-3-6-9~ hoặc ~1-5-6-9~.