根付き木が与えられます。各頂点は 1 から n まで番号が付けられており、pi は頂点 i の親、ci は敬愛フラグです。ci = 1 のとき頂点 i は祖先を敬愛しておらず、ci = 0 のときすべての祖先を敬愛しています。根の pi は -1 です。

以下の条件を満たす非根頂点を 1 つ選び削除を繰り返します。

• 親を敬愛していない。
• すべての子が自分を敬愛していない（子がいない場合も可）。
• 複数ある場合は番号最小を選択。

削除された頂点 v の子は v の親に付け替わります。この操作を条件を満たす頂点がなくなるまで繰り返し、削除された頂点を番号順に出力してください。

入力形式

n
p₁ c₁
p₂ c₂
⋯
pₙ cₙ

1 ≤ n ≤ 10⁵

出力形式

削除された頂点を空白区切りで昇順に出力。削除対象が 1 つもない場合は -1 を出力。

例 1

5
3 1
1 1
-1 0
2 1
3 0

1 2 4

例 2

5
-1 0
1 1
1 1
2 0
3 0

-1

解法の概要

削除可能な頂点は「祖先を敬愛せず、かつ子から敬愛されていない」頂点に限定されます。したがって以下の手順で効率的に列挙できます。

1. 各頂点が祖先を敬愛していないかどうかを disrespect[i] = (c[i] == 1) で記録。
2. 子から敬愛されているかどうかを respected[i] で管理。
   子 j が c[j] == 0 のとき respected[i] = true とする。
3. disrespect[i] == true かつ respected[i] == false である非根頂点を番号昇順で収集して出力。

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
int parent[MAXN], flag[MAXN];
bool disrespect[MAXN], respected[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    int root = -1;
    for (int i = 1; i <= n; ++i) {
        cin >> parent[i] >> flag[i];
        if (parent[i] == -1) root = i;
        disrespect[i] = (flag[i] == 1);
        respected[i] = false;
    }
    for (int i = 1; i <= n; ++i) {
        if (flag[i] == 0 && parent[i] != -1) {
            respected[parent[i]] = true;
        }
    }
    vector<int> erased;
    for (int i = 1; i <= n; ++i) {
        if (i == root) continue;
        if (disrespect[i] && !respected[i]) {
            erased.push_back(i);
        }
    }
    if (erased.empty()) {
        cout << -1 << '\n';
    } else {
        sort(erased.begin(), erased.end());
        for (size_t i = 0; i < erased.size(); ++i) {
            if (i) cout << ' ';
            cout << erased[i];
        }
        cout << '\n';
    }
    return 0;
}

このアルゴリズムは各頂点を定数回しか参照しないため、時間計算量は O(n log n)（ソート分）で、十分高速です。