3. BOI 2021 - From Hacks to Snitches
Không thể sống chỉ nhờ giải thưởng từ các cuộc thi tin học, bạn quyết định bước vào giới nghệ thuật — chính xác hơn là đột nhập một bảo tàng để bắt đầu sự nghiệp trộm tác phẩm nghệ thuật. Không may, bảo tàng này được canh gác khá cẩn mật: có \(K\) người bảo vệ đi tuần trong tòa nhà, mỗi người đi theo một đường khép kín đơn của riêng mình.
Để lên kế hoạch, bạn dùng một bản đồ mô tả bảo tàng bằng \(M\) hành lang nối \(N\) góc, được đánh số từ \(1\) đến \(N\). Bạn bắt đầu ở góc \(1\), còn mục tiêu — một hiện vật quý giá — nằm ở góc \(N\). Từ bất kỳ góc nào cũng có thể đi đến mọi góc khác, nhưng bạn chưa biết có thể đến mục tiêu mà không bị phát hiện hay không. Để không bị phát hiện, bạn không bao giờ được ở cùng một góc với người bảo vệ, cũng không được đi ngang qua một người bảo vệ trong hành lang.
May mắn thay, bạn đã lấy được lịch tuần tra nên biết vị trí ban đầu và lộ trình của từng người bảo vệ. Mỗi phút, người bảo vệ đi từ vị trí hiện tại đến góc tiếp theo trên lộ trình của mình; trong cùng khoảng thời gian đó, bạn có thể đứng yên hoặc đi đến một góc kề với góc hiện tại. Bạn nhận thấy lộ trình của hai người bảo vệ bất kỳ không có góc chung, và cả vị trí xuất phát lẫn mục tiêu của bạn đều không nằm trên bất kỳ lộ trình nào.
Hãy tính thời gian ít nhất, tính bằng phút, để đến mục tiêu an toàn mà không bị phát hiện, hoặc xác định rằng điều đó là không thể. Khi đến được hiện vật, bạn sẽ mở cửa sổ và rời bảo tàng bằng bộ đồ bay có cánh đã giành được trong cuộc thi tin học quốc gia, nên không cần lập kế hoạch cho đường quay về. Tất nhiên, là một tên trộm lịch thiệp, bạn sẽ không bao giờ đụng đến những người bảo vệ!
Dữ liệu vào
Dòng đầu chứa hai số nguyên \(N\) và \(M\). Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(u\) và \(v\) (\(1\le u,v\le N\), \(u\ne v\)), cho biết có một hành lang nối trực tiếp góc \(u\) với góc \(v\). Giữa hai góc bất kỳ có nhiều nhất một hành lang nối trực tiếp.
Dòng tiếp theo chứa số nguyên \(K\). Tiếp theo là \(K\) dòng mô tả lộ trình của các người bảo vệ. Dòng thứ \(i\) bắt đầu bằng số nguyên \(\ell_i\), là số góc khác nhau trên lộ trình của người bảo vệ thứ \(i\), rồi đến \(\ell_i\) số nguyên đôi một khác nhau \(v_1,\ldots,v_{\ell_i}\), theo thứ tự người đó đi qua. Người bảo vệ bắt đầu tại \(v_1\), sau một phút đến \(v_2\), và cứ tiếp tục như vậy; sau \(\ell_i\) phút, người đó trở lại \(v_1\).
Dữ liệu ra
In một dòng chứa một số nguyên là thời gian ít nhất, tính bằng phút, để đến mục tiêu an toàn, hoặc chuỗi impossible nếu không có cách nào thực hiện được.
Ràng buộc
- \(1\le N\le250\,000\).
- \(1\le M\le3\,000\,000\).
- \(3\le\ell_i\le1\,500\) với mỗi người bảo vệ \(i\).
- \(\ell_1+\cdots+\ell_K\le2\,750\).
- Có thể đi từ một góc bất kỳ đến mọi góc khác qua các hành lang.
- Mỗi lộ trình là một đường khép kín đơn đi theo các hành lang; các lộ trình không có góc chung và không đi qua góc \(1\) hoặc góc \(N\).
Phân nhóm
- \(5\) điểm: \(N,M\le100\,000\), \(K=1\), \(\ell_1\le125\).
- \(10\) điểm: \(N,M\le100\,000\), \(\ell_1+\cdots+\ell_K\le125\), và không có hành lang nào nối lộ trình của hai người bảo vệ khác nhau.
- \(10\) điểm: \(\ell_i\le200\) với mọi \(i\), \(\ell_1+\cdots+\ell_K\le350\), và không có hành lang nào nối lộ trình của hai người bảo vệ khác nhau.
- \(10\) điểm: không có hành lang nào nối lộ trình của hai người bảo vệ khác nhau.
- \(25\) điểm: \(\ell_1+\cdots+\ell_K\le125\).
- \(20\) điểm: \(\ell_i\le200\) với mọi \(i\) và \(\ell_1+\cdots+\ell_K\le350\).
- \(20\) điểm: không có ràng buộc thêm.
Ví dụ
Ví dụ 1
Input
6 6
1 2
2 3
3 4
4 5
5 2
5 6
1
4 3 2 5 4Output
4Giải thích
Hình sau minh họa ví dụ thứ nhất:
Góc có người bảo vệ lúc đầu được viền đậm, còn dấu chân biểu diễn lộ trình tuần tra. Một cách đi tối ưu là chờ ở vị trí xuất phát, góc \(1\), trong một phút, rồi lần lượt đi đến các góc \(2\), \(5\) và cuối cùng là \(6\) mà không chờ thêm.
Ví dụ 2
Input
6 6
1 2
2 3
3 4
4 5
5 2
5 6
1
4 4 5 2 3Output
5Giải thích
Bố trí bảo tàng giống ví dụ thứ nhất, nhưng vị trí xuất phát và chiều đi của người bảo vệ khác đi. Một cách đi tối ưu là lần lượt qua các góc \(1,2,3,4,5,6\).
Ví dụ 3
Input
11 13
1 2
2 3
3 4
4 2
3 5
5 6
6 7
7 5
6 8
8 9
9 10
10 8
9 11
3
3 4 2 3
3 7 6 5
3 10 8 9Output
impossibleGiới hạn
Thời gian: \(4\) giây. Bộ nhớ: \(512\) MiB.