Problem
Tại thành phố N, trong hoàn cảnh không rõ ràng, lãnh thổ của một trong những nhà máy đã biến thành một khu vực dị thường. Tất cả các lối vào lãnh thổ đã bị chặn, và nó được gọi là khu công nghiệp. Có
N tòa nhà trong khu công nghiệp, một số tòa nhà được nối với nhau bằng đường bộ. Mọi con đường đều có thể đi theo cả hai hướng.
Kẻ theo dõi mới làm quen được giao nhiệm vụ đến nhà kho trong khu công nghiệp. Anh ta tìm thấy một số bản đồ về lãnh thổ của khu công nghiệp trong kho lưu trữ điện tử. Vì các bản đồ được biên soạn bởi những người khác nhau nên mỗi bản đồ chỉ chứa thông tin về một số con đường của khu công nghiệp. Cùng một con đường có thể xuất hiện trên nhiều bản đồ.
Trên đường đi, kẻ theo dõi có thể tải một thẻ từ kho lưu trữ về điện thoại di động. Khi bạn tải xuống bản đồ mới, bản đồ trước đó không được lưu trong bộ nhớ của điện thoại. Kẻ theo dõi chỉ có thể di chuyển dọc theo những con đường được đánh dấu trên bản đồ hiện được tải. Mỗi lần tải xuống bản đồ có giá 1 rúp. Để giảm thiểu chi phí, kẻ theo dõi cần chọn một tuyến đường như vậy để tải xuống bản đồ ít lần nhất có thể. Stalker có thể tải xuống cùng một bản đồ nhiều lần và bạn sẽ phải trả tiền cho mỗi lần tải xuống. Ban đầu, không có thẻ trong bộ nhớ của điện thoại di động.
Yêu cầu viết chương trình tính toán chi phí tối thiểu cần thiết để một kẻ theo dõi có thể đi từ cổng vào khu công nghiệp đến nhà kho.
Đầu vào:
- dòng đầu tiên chứa 2 số tự nhiên
N và
K (
\(2 <= N <= 2000 \ );
\(1 <= K <= 2000\)) — số tòa nhà khu công nghiệp và số lượng bản đồ tương ứng. Lối vào khu công nghiệp nằm trong tòa nhà có số
1 và nhà kho — trong tòa nhà số
N.
- trong các dòng sau có thông tin về các thẻ có sẵn. Dòng đầu tiên của phần mô tả thẻ thứ
i chứa số
ri — số đường được đánh dấu trên bản đồ thứ
i;
- rồi đến
ri chuỗi chứa hai số tự nhiên
a và
b (
\(1 <= a\),
\(b <= N\);
\(a ? b\)), nghĩa là có một con đường trên bản đồ thứ
i nối các tòa nhà
a và
b< /mã>. Tổng số đường được đánh dấu trên tất cả các bản đồ không vượt quá 300.000 (\(r_1 + r_2 + … + r_K <= 300.000\)).
Đầu ra: in một số duy nhất — số tiền tối thiểu của chi phí của kẻ theo dõi. Nếu không thể đến kho, hãy in số –1.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
12 4
4
16
24
79
10 12
3
14
7 11
36
3
25
4 11
8 9
5
3 10
10 7
7 2
12 3
5 12 |
3 |