ArrayList<Integer>[] g = new ArrayList[n];
for (int i = 0; i < n; ++i) {
    g[i] = new ArrayList<Integer>();
}
 
for (int i = 0; i < m; ++i) {
    int a = nextInt() - 1;
    int b = nextInt() - 1;
    g[a].add(b);
    g[b].add(a);
}
 
int[] dist = new int[n];
LinkedList<Integer> q = new LinkedList<>();
Arrays.fill(dist, Integer.MAX_INT);
 
dist[0] = 0;
q.addLast(0);
 
while (q.size() > 0) {
    int v = q.removeFirst();
    for (int i = 0; i < g[v].size(): ++i) {
        int to = g[v].get(i);
        if (dist[to] < dist[v] + 1) {
            dist[to] = dist[v] + 1;
            q.addLast(to);
        }
    }
}

QXJyYXlMaXN0PEludGVnZXI+W10gZyA9IG5ldyBBcnJheUxpc3Rbbl07CmZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICBnW2ldID0gbmV3IEFycmF5TGlzdDxJbnRlZ2VyPigpOwp9Cgpmb3IgKGludCBpID0gMDsgaSA8IG07ICsraSkgewogICAgaW50IGEgPSBuZXh0SW50KCkgLSAxOwogICAgaW50IGIgPSBuZXh0SW50KCkgLSAxOwogICAgZ1thXS5hZGQoYik7CiAgICBnW2JdLmFkZChhKTsKfQoKaW50W10gZGlzdCA9IG5ldyBpbnRbbl07CkxpbmtlZExpc3Q8SW50ZWdlcj4gcSA9IG5ldyBMaW5rZWRMaXN0PD4oKTsKQXJyYXlzLmZpbGwoZGlzdCwgSW50ZWdlci5NQVhfSU5UKTsKCmRpc3RbMF0gPSAwOwpxLmFkZExhc3QoMCk7Cgp3aGlsZSAocS5zaXplKCkgPiAwKSB7CiAgICBpbnQgdiA9IHEucmVtb3ZlRmlyc3QoKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgZ1t2XS5zaXplKCk6ICsraSkgewogICAgICAgIGludCB0byA9IGdbdl0uZ2V0KGkpOwogICAgICAgIGlmIChkaXN0W3RvXSA8IGRpc3Rbdl0gKyAxKSB7CiAgICAgICAgICAgIGRpc3RbdG9dID0gZGlzdFt2XSArIDE7CiAgICAgICAgICAgIHEuYWRkTGFzdCh0byk7CiAgICAgICAgfQogICAgfQp9