p321.ans1
======================
2
1 2

=================
p321.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<vector<pair<int, int>>> adj;

void read() {
    cin >> n;
    adj.assign(n, {});
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;

        string type;
        getline(cin, type);
        if(type[1] == 'a') {
            adj[u].emplace_back(v, i);
            adj[v].emplace_back(u, i);
        } else if(type[1] == 'p') {
            adj[u].emplace_back(v, -1);
            adj[v].emplace_back(u, -1);
        }
    }
}

void solve() {
    // All channels point towards Kat (node 1), forming a tree rooted there.
    // For a node at depth d (the path to Kat has d edges) we need at least
    // ceil(d / 2) of those edges protected, i.e. at most floor(d / 2) may
    // stay almost protected. We DFS from the root and maintain the set
    // almost_protected of the almost-protected edges on the current
    // root-to-node path, keyed by (depth_of_edge, edge_index).
    //
    // When entering a node at depth d, if the number of almost-protected
    // edges on the path exceeds floor(d / 2), we must upgrade one of them.
    // We greedily upgrade the shallowest such edge (smallest depth), since
    // it is shared by the most descendants and therefore helps the most
    // subtrees at once; that edge is removed from the set and recorded in
    // ans. Backtracking removes each edge we added on the way down.

    vector<int> ans;
    set<pair<int, int>> almost_protected;

    function<void(int, int, int)> dfs = [&](int u, int p, int depth) {
        if(almost_protected.size() * 2 > depth) {
            auto lowest = almost_protected.begin();
            ans.push_back(lowest->second);
            almost_protected.erase(lowest);
        }

        for(auto [v, i]: adj[u]) {
            if(v == p) {
                continue;
            }
            if(i != -1) {
                almost_protected.insert({depth, i});
            }

            dfs(v, u, depth + 1);
            if(i != -1 && almost_protected.count({depth, i})) {
                almost_protected.erase({depth, i});
            }
        }
    };

    dfs(0, -1, 0);

    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " \n"[i + 1 == ans.size()];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p321.in1
======================
5
5 1 almost protected
3 1 almost protected
2 3 protected
4 3 almost protected

=================
statement.txt
======================
321. The Spy Network
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



The network of spies consists of N intelligence officers. They are numbered with the code numbers from 1 to N so that nobody could discover them. The number 1 belongs to the radiowoman Kat. There is exactly N - 1 communication channels between the spies. It is known that a message from any spy to Kat can reach her. All channels are unidirectional.

A channel can have one of two types: protected and almost protected. It is known that a message will not be intercepted almost surely by the hostile security service if at least half of the channels along the path to radiowoman Kat are protected. What is the minimum number of channels to be made protected from almost protected, so that any message from any spy will not be intercepted almost surely ? What are those channels?

Input
The first line of the input contains the integer number N (1 ≤ N ≤ 200000). The following N - 1 lines contain the description of the communication channels. Each channel is described by a pair of the code numbers of spies (the direction of the channel is from the first spy to the second one) and the parameter pi. If pi = protected, the channel is protected and if pi = almost protected, the channel is almost protected.

Output
Write the number of channels to be converted to protected to the first line of the output. To the next line write numbers of channels to be made protected. If there are several solutions, choose any of them.

Example(s)
sample input
sample output
5
5 1 almost protected
3 1 almost protected
2 3 protected
4 3 almost protected
2
1 2

=================
