struct Edge {
    int to, w; // w = {0, 1}
};

const int N = 100100;
vector<Edge> g[N];

vector<int> Dijkstra(int from, int n) {
    vector<int> depth(n, n);
    depth[from] = 0;
    vector<bool> used(n);

    auto connect = [&] (int start) {
        queue<int> q;
        q.push(start);
        vector<int> result;
        result.push_back(start);
        used[start] = true;
        while (q.size()) {
            int v = q.front();
            q.pop();

            for (const auto& [to, w] : g[v]) {
                if (w != 0) continue;
                if (used[to] == true) continue;
                used[to] = true;
                result.push_back(to);
                depth[to] = depth[start];
                q.push(to);
            }
        }
        return result;
    };

    queue<int> q;
    q.push(from);
    while (q.size()) {
        int v = q.front();
        q.pop();

        auto ne = connect(v);
        for (int currentVertex : ne) {
            for (const auto& [to, w] : g[currentVertex]) {
                if (depth[to] > depth[currentVertex] + w) {
                    depth[to] = depth[currentVertex] + w;
                    q.push(to);
                }
            }
        }
    }
    return depth;
}