#1357. TRIP2015

Vương quốc của HP gồm thành phố. HP là một nhà vua rất thông minh nên đã chia thành phố thành cụm, mỗi cụm gồm có thành phố, một thành phố có thể nằm trong nhiều cụm. Sau đó HP yêu cầu xây tất cả các con đường nối hai thành phố bất kì trong mỗi cụm thành phố, vậy nên trong mỗi cụm sẽ có tất cả con đường.

Thủ đô của vương quốc là thành phố và cũng là nơi cư ngụ của HP. HP muốn thăm một người bạn ở thành phố và thắc mắc HP phải đi qua ít nhất bao nhiêu thành phố để đến được đó.

Dữ liệu vào:

• Dòng đầu tiên gồm ba số nguyên , số thành phố, , số thành phố trong mỗi cụm và , số cụm thành phố;
• dòng tiếp theo, mỗi dòng gồm số nguyên là các thành phố trong cụm đó.

Các số trên một dòng của Dữ liệu vào được ghi cách nhau bởi dấu cách.

Dữ liệu ra:

• Ghi ra một số nguyên duy nhất là kết quả bài toán, nếu không có đường đi in ra .

Ví dụ:

Dữ liệu vào:

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

Dữ liệu ra:

2

Dữ liệu vào:

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

Dữ liệu ra:

3