OIG IV - war

// https://szkopul.edu.pl/problemset/problem/75WTu9ZZJlfrT_dO204-8djk/site/?key=statement
// OIG IV 2 etap

#include <algorithm>
#include <iostream>
#include <vector>

constexpr int sizik = 1000 * 1001;

int n, m, k;

int rep[sizik];
int kol_rep[sizik];
int ans2[sizik];
int v[sizik];

int Find(int a) {
    if (rep[a] == a) {
        return a;
    }

    int res = Find(rep[a]);

    rep[a] = res;
    return res;
}

void Union(int a, int b) {
    int res1 = Find(a);
    int res2 = Find(b);

    rep[res1] = res2;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> n >> m >> k;

    for (int i = 1; i <= n; i++) {
        int a;
        std::cin >> a;

        v[i] = a;

        if (kol_rep[a] == 0) {
            kol_rep[a] = i;
        }

        rep[i] = kol_rep[a];
    }

    for (int i = 0; i < m; i++) {
        int a, b;
        std::cin >> a >> b;

        if (a == b) {
            continue;
        }

        if (kol_rep[a] == 0) {
            continue;
        }

        if (kol_rep[b] != 0) {
            Union(kol_rep[a], kol_rep[b]);
            kol_rep[a] = 0;

            continue;
        }

        kol_rep[b] = kol_rep[a];
        kol_rep[a] = 0;
    }

    for (int i = 1; i <= k; i++) {
        ans2[kol_rep[i]] = i;
    }

    for (int i = 1; i <= n; i++) {
        int ans = ans2[Find(rep[i])];
        std::cout << ans << ' ';
    }

    std::cout << '\n';

    return 0;
}