Subtask 1 ~(n \le 4)~:

• Vì kích cỡ ma trận bị giới hạn bởi ~4~ nên số ô tối đa của ma trận ~A~ là ~16~ ô.

• Nhận xét : Cho ~B~ và ~B'~ là ~2~ ma trận vuông có kích thước ~n \times n~ với mỗi ô trên ma trận ~B~ có giá trị là ~1~ số nguyên không âm và ~B'~ là ma trận thu được sau khi thay toàn bộ các số nguyên dương trên ma trận ~B~ bằng số ~1~. Với số nguyên dương ~k~ bất kỳ, dễ thấy nếu ~B^k~ là ma trận toàn ~0~ thì ~B'^k~ cũng là ma trận toàn ~0~.

• Vậy nếu đặt ~B = A~ thì ~B'~ chỉ có tối đa ~2^{16}~ trạng thái do mỗi ô phải có giá trị ~0~ hoặc ~1~, ta coi mỗi trạng thái của ma trận ~B'~ là ~1~ đỉnh trên đồ thị và dựng cạnh có hướng giữa các cặp đỉnh ~B'~ và ~(B' \times A)'~, vậy ta cần tìm đường đi ngắn nhất giữa đỉnh gốc và đỉnh ma trận ~B'~ toàn ~0~ trên đồ thị (hoặc in ra ~-1~ nếu giữa ~2~ đỉnh không tồn tại đường đi), bài có thể giải bằng thuật toán BFS với độ phức tạp ~O(2^{n^2} * n^3)~ với ~n^3~ là độ phức tạp của một phép nhân ma trận.

Subtask 2 ~(n \le 60)~:

Cách 1 (dựa vào phán đoán):

• Vì tác giả không bắt in ra kết quả mod ~10^9+7~ (hoặc giảm tải output theo cách khác) nên rất có thể kết quả của bài phải nằm trong giới hạn của biến long long.

• Đặt ~X~ là ~1~ số nguyên vừa đủ to để ~2^X~ vượt quá giới hạn của biến long long, chẳng hạn như ~X = 70~.

• Ta tính trước tất cả các ma trận ~A~ có dạng ~A^{2^x}~ với ~x~ là số nguyên trong khoảng ~[0, X]~, rồi dùng kỹ thuật binary lifting để tìm ra số ~k-1~ (là lũy thừa lớn nhất sao cho ma trận ~A~ còn lại ít nhất ~1~ số nguyên dương), nếu kết quả ~k~ tìm được vô tình vượt quá giới hạn của long long thì ta in ra ~-1~. Độ phức tạp của cách làm này là ~O(n^3 \times X)~.

Cách 2 (dựa vào nhận xét):

• Nhận xét : Trên thực tế có thể chứng minh được rằng nếu ~k~ tồn tại thì phải thỏa mãn ~k \le n~, tuy nhiên phần chứng minh sẽ được để lại cho thí sinh tự suy nghĩ. Từ nhận xét này, dễ thấy ta chỉ cần tính hết ~n~ lũy thừa đầu tiên của ma trận ~A~ là đủ biết kết quả, độ phức tạp của cách làm này là ~O(n^4)~.

Subtask 3:

• Để hoàn thành subtask này, chúng ta cần thay đổi góc nhìn về bài toán. Ta coi ~A~ như là ~1~ adjacency matrix của đồ thị tương ứng gọi là ~G~ (vì ~A~ chỉ gồm ~0~ hoặc ~1~). Lúc này, ô ~(i, j)~ trong ma trận ~A^k~ sẽ cho biết số đường đi độ dài ~k~ giữa ~2~ đỉnh ~i, j~ trên đồ thị ~G~.

• Nếu đồ thị ~G~ mà có chu trình (tính cả self-loop và chu trình có độ dài ~2~) thì kết quả sẽ là ~-1~, vì luôn tồn tại ít nhất ~1~ đường đi có độ dài ~k~ giữa ~2~ đỉnh nào đó cùng nằm trên chu trình này. Vì vậy nếu ~k~ tồn tại thì ~G~ phải là ~1~ đồ thị ~DAG~ và đường đi dài nhất trên đồ thị ~G~ có độ dài chính bằng ~k-1~. Tìm đường đi dài nhất trên đồ thị ~DAG~ là ~1~ bài tập kinh điển từng xuất hiện trong series atcoder dp và được giải bằng ~DFS~ với độ phức tạp ~O(n+m)~.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define fo(i, a, b) for(int i = a; i <= b; i++)
#define _fo(i, a, b) for(int i = a; i >= b; i--)
#define foa(i, a) for (auto &i : a)
#define sz(a) ((int) a.size())
#define all(a) begin(a), end(a)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mk(x, y) make_pair(x, y)

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAX = 5e5+5;
const int LOG = 20;
const ll MOD = 1e9+7;
const ll INF = 1e9;
const ll SQRT = 4e6;

int n, m;
int f[MAX];
vector<int> adj[MAX];
int color[MAX];

void dfs(int v) {
    f[v] = 0;
    foa(u, adj[v]) {
        if(f[u] == -1) dfs(u);
        f[v] = max(f[v], f[u]+1);
    }
}

bool cycle(int v) {
    if(color[v] == 1) return true;      
    color[v] = 1;
    foa(u, adj[v]) {
        if(color[u] == 2) continue;
        if(cycle(u)) return true;
    }
    color[v] = 2;
    return false;
}

bool check() {
    fo(v, 1, n) {
        if(cycle(v)) return false;
    }
    return true;
}

signed main() { 
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    fo(i, 1, m) {
        int v, u;
        cin >> v >> u;
        adj[v].pb(u);
    }

    if(!check()) cout << -1;
    else {
        fill(f, f+n+1, -1); 
        fo(i, 1, n) {
            if(f[i] == -1) dfs(i);
        }
        int res = 0;
        fo(i, 1, n) res = max(res, f[i]);
        cout << res+1;  
    }
}