ABC 401

vector<pair<char, int>> runLengthEncode(const string& input) {
    vector<pair<char, int>> encoded;
    int size = input.size();
    for (int i = 0; i < size; ++i) {
        int count = 1;
        while (i + 1 < size && input[i] == input[i + 1]) {
            ++i;
            ++count;
        }
        encoded.emplace_back(input[i], count);
    }
    return encoded;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    string S;
    cin >> N >> K >> S;

    rep(i, N) {
        if (i + 1 < N && S[i] == '?' && S[i + 1] == 'o') {
            S[i] = '.';
        }
        if (i + 1 < N && S[i] == 'o' && S[i + 1] == '?') {
            S[i + 1] = '.';
        }
    }

    int no = 0;
    for (char c : S)
        if (c == 'o')
            no++;
    if (no == K) {
        rep(i, N) if (S[i] == '?') S[i] = '.';
        cout << S << endl;
        return;
    }

    auto ps = runLengthEncode(S);
    int m = 0;
    for (auto [c, num] : ps) {
        if (c == 'o')
            m += num;
        if (c == '?')
            m += (num + 1) / 2;
    }

    if (m > K) {
        cout << S << endl;
        return;
    }

    for (auto [c, num] : ps) {
        if (c != '?') {
            rep(i, num) cout << c;
            continue;
        }

        if (num % 2 == 0) {
            rep(i, num) cout << '?';
        } else {
            rep(i, num) {
                cout << (i % 2 == 0 ? 'o' : '.');
            }
        }
    }
    cout << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vvint graph(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    dsu uf(N);
    vint suteru(N, 0);
    int cnt = 0;
    rep(i, N) {
        for (int nx : graph[i]) {
            if (nx < i) {
                uf.merge(nx, i);
            } else {
                if (suteru[nx])
                    continue;
                suteru[nx] = 1;
                cnt++;
            }
        }
        if (suteru[i])
            cnt--;
        int ans = cnt;
        if (uf.size(0) != i + 1)
            ans = -1;
        cout << ans << endl;
    }
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vvint graph(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    dsu uf(N), neigh(N);
    rep(i, N) {
        for (int nx : graph[i]) {
            if (nx < i) {
                uf.merge(nx, i);
            }
            neigh.merge(nx, i);
        }

        int ans = -1;
        if (uf.size(0) == i + 1) {
            ans = neigh.size(0) - uf.size(0);
        }
        cout << ans << endl;
    }
}