Sem_2_Task_4

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

struct Edge;

const int64_t INF = int64_t(1e15);

namespace {
    using NumsVec = std::vector<int64_t>;
    using VecNumsVec = std::vector<NumsVec>;
    using BoolVec = std::vector<bool>;
    using EdgeVec = std::vector<Edge>;
    using VecEdgeVec = std::vector<EdgeVec>;
}

struct Edge {
    Edge() = default;
    Edge(std::pair<size_t, size_t> edge) : from(edge.first), to(edge.second) {};
    Edge(size_t i, size_t j) : from(i), to(j) {};

    bool operator==(const Edge& other) const {
        return from == other.from && to == other.to;
    }

    Edge Reverse() {
        return Edge(to, from);
    }

    size_t from = 0;
    size_t to = 0;
};

std::istream& operator>>(std::istream& input, Edge& edge) {
    input >> edge.from >> edge.to;
    --edge.from;
    --edge.to;
    return input;
}

void InputEdges(std::vector<Edge>& edges) {
    for (auto& edge : edges) {
        std::cin >> edge;
    }
}

template<>
struct std::hash<Edge> {
    size_t operator()(const Edge& p) const {
        return p.from * p.to;
    }
};

std::ostream& operator<<(std::ostream& output, NumsVec& vec) {
    for (auto elem : vec) {
        std::cout << elem + 1 << " ";
    }
    return output;
}

struct Graph {
    Graph(size_t n) : size(n), neighbours(n), visited(n, false), color(n, 0),
    top_sort(n, 0), top_sort_pos(n - 1), d(n, NumsVec(n, INF)) {};

    Graph(size_t n, EdgeVec& edges) : size(n), visited(n, false), color(n, 0),
    top_sort(n, 0), top_sort_pos(n - 1), d(n, NumsVec(n, INF)), matrix(n, NumsVec(n, 1)), neighbours(n) {
        for (auto edge : edges) {
            neighbours[edge.from].push_back(edge);
        }
        for (size_t v = 0; v < n; ++v) {
            d[v][v] = 0;
        }
    };

    size_t size = 0;
    bool cycle = false;

    VecEdgeVec neighbours;
    VecNumsVec matrix;
    BoolVec visited;
    NumsVec color;
    NumsVec top_sort;
    VecNumsVec d;
    size_t sum_w = 0;
    size_t top_sort_pos = 0;
};

void TopSort(Graph& g, size_t v) {
    g.visited[v] = true;
    for (auto [from, to] : g.neighbours[v]) {
        if (!g.visited[to]) {
            TopSort(g, to);
        }
    }
    g.top_sort[g.top_sort_pos] = v;
    --g.top_sort_pos;
}

void CountDistances(Graph& g) {
    for (size_t v : g.top_sort) {
        for (auto [from, to] : g.neighbours[v]) {
            for (size_t u = 0; u < g.size; ++u) {
                g.d[u][to] = std::min(g.d[u][to], g.d[u][v] + 1);
            }
        }
    }
}

int main() {
    size_t n, m;
    std::cin >> n >> m;
    EdgeVec edges(m);
    InputEdges(edges);
    Graph g(n, edges);
    for(size_t v = 0; v < g.size; ++v) {
        if (!g.visited[v]) {
            TopSort(g, v);
        }
    }
    CountDistances(g);
    for (size_t u = 0; u < n; ++u) {
        for (size_t v = 0; v < n; ++v) {
            std::cout << (g.d[u][v] == INF ? -1 : g.d[u][v]) << " ";
        }
        std::cout << std::endl;
    }
}