HA_58

/*

Доказательство условия про два ребра:

- inB[v] + inC[v] считаем только по "живым" годам.

- Замечание: когда алгоритм закончился, для любой вершины
inB[v] == 1 и inC[v] == 1.

- Действительно, исходящих рёбер каждого цвета ровно |V|,
а условие задачи требует ≥1 входа каждого цвета;

- поэтому два входа одного цвета в одну вершину невозможны.
*/


/*************************************************************
 *  Для каждого года i есть два ориентированных ребра
 *      Ai ──(blue)──► Bi
 *      Ai ──(red) ─► Ci
 *
 *  Оставляем подмножество лет  S.  Требование условия:
 *
 *  в каждую вершину входит ≥ 1 blue-и ≥ 1 red-ребро.
 *  Поэтому в корректном ответе в вершину не может
 *  входить два ребра одного цвета – иначе какой-то
 *  вершине не хватило бы входов (принцип Дирихле).
 *
 *  Алгоритм “листопад”.
 *  ------------------------------------
 *  • inB[v], inC[v] –- число blue/red входов из ещё
 *    «живых» лет;
 *  • occCnt[v] – число «живых» лет,
 *    где v встречается в A,B или C.
 *  • Очередь Q из вершин, у которых  inB==0 || inC==0.
 *  • Пока Q не пуста:
 *        v = pop()
 *        если  occCnt[v] == 0     continue
 *        для каждого года idx, где v встречается
 *            if removed[idx]      continue
 *            removed[idx] = true
 *            --occCnt[ Aidx ], occCnt[ Bidx ], occCnt[ Cidx ]
 *            --inB[ Bidx ],  --inC[ Cidx ];
 *            если какая-то вершина осталась без входа
 *            ⇒ push в очередь
 *  ответ = удаленные года.
 *  Работает O(N) памяти/времени:
 *  каждый год и вершина обрабатываются максимум один раз.
 *************************************************************/

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

struct Triple { int a, b, c; };

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

    int N;
    if (!(cin >> N)) return 0;

    vector<Triple> yr(N);
    for (int i = 0; i < N; ++i) cin >> yr[i].a;
    for (int i = 0; i < N; ++i) cin >> yr[i].b;
    for (int i = 0; i < N; ++i) cin >> yr[i].c;

    const int SZ = N + 1;                 // вершины 1..N
    vector<int> inB(SZ, 0), inC(SZ, 0), occCnt(SZ, 0);
    vector<vector<int>> occ(SZ);          // годы, где встречается вершина

    // собираем "статистику"
    for (int i = 0; i < N; ++i) {
        auto [a,b,c] = yr[i];
        ++inB[b]; ++inC[c];
        for (int v : {a,b,c}) {
            ++occCnt[v];
            occ[v].push_back(i);
        }
    }

    queue<int> Q;
    vector<char> inQ(SZ, 0);
    auto push_if_bad = [&](int v) {
        if (occCnt[v] && (inB[v]==0 || inC[v]==0) && !inQ[v]) {
            Q.push(v); inQ[v] = 1;
        }
    };
    for (int v = 1; v <= N; ++v) push_if_bad(v);

    vector<char> removedYr(N, 0);
    int removedCnt = 0;

    while (!Q.empty()) {
        int v = Q.front(); Q.pop(); inQ[v] = 0;
        if (occCnt[v]==0) continue;
        // могла обнулиться раньше

        for (int idx : occ[v]) {
            if (removedYr[idx]) continue;
            removedYr[idx] = 1;
            ++removedCnt;

            auto [a,b,c] = yr[idx];

            // убрали год – вершины в нём проявляются на год меньше */
            for (int u : {a,b,c}) {
                if (--occCnt[u]==0) inQ[u]=0;
                // совсем исчезла
            }

            // у целей ушёл вход
            if (--inB[b]==0) push_if_bad(b);
            if (--inC[c]==0) push_if_bad(c);
        }
    }

    cout << removedCnt << '\n';
    return 0;
}