Mọi người đều biết rằng Cần Thơ có \(n\) công viên, \(m\) con mèo và \(n + m\) con đường nối các công viên. Mèo là động vật rất lãnh thổ nên ở mỗi con đường có nhiều nhất một con mèo. Nó tuần tra con đường bằng cách hung dữ tấn canh mọi người đi theo một hướng của con đường đó, nhưng từ những người đi theo hướng ngược lại, nó đòi vuốt ve trước khi cho họ đi qua. Thành phố Cần Thơ, nhận thức được tình huống này, đã đảm bảo rằng người dân có thể đến bất kỳ công viên nào từ bất kỳ công viên nào khác chỉ sử dụng \(n\) con đường không có mèo.
Trung tâm Du lịch đã quyết định mở một tour gọi là Tour Mèo ở Cần Thơ. Khách tham quan tour sẽ có thể vuốt ve mọi con mèo ở Cần Thơ và quay lại vị trí xuất phát để họ có thể làm lại tất cả. Để đảm bảo khách du lịch không bị lạc, trung tâm du lịch sẽ đặt biển báo ở mỗi con đường cho họ biết con đường nào họ nên đi tiếp theo, vì vậy Tour Mèo không thể đi cùng một con đường hai lần (kể cả theo hướng ngược lại). Rõ ràng, khách du lịch mong đợi được vuốt ve mọi con mèo, không có con mèo nào tấn canh họ và tour càng ngắn càng tốt.
Giúp trung tâm du lịch tìm độ dài của Tour Mèo ngắn nhất có thể hoặc nói rằng không thể thực hiện.
Dữ liệu vào
- Dòng đầu tiên chứa các số nguyên \(n, m\) \((1 \le n \le 2 \times 10^4, 0 \le m \le 2 \times 10^4)\), số lượng công viên và mèo.
- \(n\) dòng tiếp theo chứa các cặp \(a, b\) \((1 \le a, b \le n)\) mô tả các con đường không có mèo. Lưu ý rằng có thể \(a = b\) hoặc hai hoặc nhiều con đường nối cùng các công viên.
- \(m\) dòng tiếp theo chứa các cặp \(x, y (1 \le x, y \le n)\) mô tả các con đường nơi một con mèo cho phép đi từ \(x\) đến \(y\). Lưu ý rằng có thể hai hoặc nhiều con đường nối cùng các công viên.
Dữ liệu ra
- Trong dòng đầu tiên và duy nhất, xuất ra độ dài của Tour Mèo ngắn nhất có thể hoặc "-1" nếu không có Tour Mèo nào tồn tại.
Chấm điểm
Subtask | Điểm | Ràng buộc |
---|---|---|
1 | 11 | \(n, m \le 20\) |
2 | 41 | Tồn tại một con đường nối một công viên với chính nó không được tuần tra bởi mèo |
3 | 68 | Không có ràng buộc bổ sung. |
Input 1
5 1
3 1
3 2
3 4
3 5
2 4
3 5
Output 1
2
Input 2
6 7
3 2
5 3
1 4
6 1
5 6
4 2
4 5
1 2
4 2
2 6
3 1
1 6
6 4
Output 2
10
Input 3
7 3
4 1
4 3
6 4
2 6
5 2
5 7
4 4
3 6
4 1
7 5
Output 3
-1
Giải thích ví dụ thứ nhất: Tour Mèo ngắn nhất là 3 → 5 → 3.
Nhận xét