Gửi bài giải
Điểm:
0,60 (OI)
Giới hạn thời gian:
1.2s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Trong bài có thể xuất hiện nhiều khái niệm mới, đầu tiên bạn cần biết về nhân ma trận.
Cho ~A~ là ~1~ ma trận vuông có kích thước ~n \times n~ và ~A~ chỉ gồm các ô có giá trị ~0~ hoặc ~1~. Tìm số nguyên dương ~k~ nhỏ nhất sao cho lũy thừa bậc ~k~ của ma trận ~A~ là ma trận gồm toàn các số ~0~, biết rằng lũy thừa của một ma trận được mô tả như sau:
Input:
- Dòng đầu gồm ~2~ số nguyên ~n~ ~(1 \leq n \leq 5 \times 10^5)~ và ~m~ ~(0 \leq m \leq 5 \times 10^5)~ trong đó ~n~ là kích thước ma trận còn ~m~ là số ô có giá trị bằng ~1~ trên ma trận ~A~.
- ~m~ dòng tiếp theo, trên mỗi dòng có một cặp số ~(i, j)~ ~(1 \leq i, j \leq n)~ là tọa độ của các ô có giá trị bằng ~1~ trên ma trận ~A~, dữ liệu đảm bảo rằng không có cặp số ~(i, j)~ nào xuất hiện ~2~ lần. Một ô có tọa độ ~(i, j)~ nếu như nó nằm tại dòng thứ ~i~ tính từ trên xuống và cột thứ ~j~ tính từ bên trái sang của ma trận ~A~, nếu toạ độ của ô không nằm trong ~m~ cặp số được cho thì ô đó mặc định có giá trị bằng ~0~.
Output:
- In ra số nguyên dương ~k~ nhỏ nhất hoặc ~-1~ nếu ~k~ không tồn tại.
Sample Input 1:
4 2
1 2
4 3
Sample Output 1:
2
Sample Input 2:
3 3
1 1
2 2
3 3
Sample Output 2:
-1
Subtask
- ~10\%~ số test có ~1 \le n \le 4~.
- ~30\%~ số test khác có ~1 \le n \le 60~.
- ~60\%~ số test còn lại không có điều kiện gì thêm.
Note
Ở Sample test 1, dễ thấy ~A^2~ là ma trận toàn ~0~.
Ở Sample test 2, ma trận ~A~ đã cho được gọi là một Identity matrix, khi lấy lũy thừa bậc ~k~ của một Identity matrix thì giá trị các ô trên ma trận hoàn toàn giữ nguyên.
Bình luận