WA#7 251st word 求助

#ifdef LOCAL
#include "all.hh"
#else
#include <bits/stdc++.h>
#define ldebug(...) (void)(__VA_ARGS__)
#define lassert(...) (void)(__VA_ARGS__)
#endif
#define FOR(i, a, b) for (ui i = a; i <= (b); ++i)
#define REP(i, a, b) for (ui i = a; i < (b); ++i)
#define RFOR(i, a, b) for (ui i = (a) + 1; i-- > (b);)
#define RREP(i, a, b) for (ui i = a; i > (b); --i)
using uc = unsigned char;
using ui = unsigned int;
using u64 = unsigned long long;
using i64 = long long;
using fp = double;
template <typename T> using nlim = std::numeric_limits<T>;
template <typename T, typename U>
inline constexpr bool ckmin(T& a, const U& b) {
    return b < a && (a = b, true);
}
template <typename T, typename U>
inline constexpr bool ckmax(T& a, const U& b) {
    return a < b && (a = b, true);
}
template <size_t N> inline void read_str(char (&s)[N], char delim = '\n') {
    std::cin >> std::ws;
    std::cin.get(s + 1, N - 1, delim);
}
// fastio begin.
#include <cctype>
#include <cstddef>
#include <string>
#include <iostream>
#include <type_traits>
#include <utility>
using uc = unsigned char;
using ui = unsigned int;
#define HAVE_FAST_IO
#define FASTIO_NO_PUNC 1
#define FASTIO_NO_ALPHA 1
#if FASTIO_NO_PUNC
#define my_isspace (c < '0')
#else
#define my_isspace (c == ' ' || c == '\n' || c == '\r')
#endif
#if FASTIO_NO_ALPHA && FASTIO_NO_PUNC
#define my_isdigit (c >= '0')
#else
#define my_isdigit std::isdigit(c)
#endif
namespace fast_i_ {
    constexpr size_t sz = 1U << 24;
    bool sgn;
    char buf[sz], *b = buf, *e = buf;
    uc c;
    inline void getch() {
        if (b == e) {
            std::cin.read(buf, sizeof(buf));
            if (std::cin.gcount() == 0) {
                c = '\n';
                return;
            }
            b = buf;
            e = buf + std::cin.gcount();
        }
        c = static_cast<uc>(*b++);
    }
    inline void read(char& r) {
        getch();
        while (my_isspace)
            getch();
        r = static_cast<char>(c);
    }
    inline void read(uc& r) {
        getch();
        while (my_isspace)
            getch();
        r = c;
    }
    inline void read(bool& r) {
        getch();
        while (!my_isdigit)
            getch();
        r = (c != '0');
    }
    template <typename T>
    inline std::enable_if_t<std::is_unsigned<T>::value &&
                            !std::is_same<T, uc>::value>
    read(T& r) {
        getch();
        while (!my_isdigit) {
            getch();
        }
        r = c & 15;
        getch();
        while (my_isdigit) {
            r = r * 10 + (c & 15);
            getch();
        }
    }
    template <typename T>
    inline std::enable_if_t<std::is_signed<T>::value &&
                            !std::is_same<T, char>::value>
    read(T& r) {
        static std::make_unsigned_t<T> n;
        read(n);
        r = sgn ? ~(n - 1) : n;
    }
    inline void read(std::string& s) {
        getch();
        while (my_isspace)
            getch();
        s = static_cast<char>(c);
        getch();
        while (!my_isspace) {
            s += static_cast<char>(c);
            getch();
        }
    }
    template <typename... Args>
    inline std::enable_if_t<(sizeof...(Args) > 1)> read(Args&&... args) {
        (read(std::forward<Args>(args)), ...);
    }
} // namespace fast_i_
namespace fast_o_ {
    constexpr size_t sz = 1U << 20;
    char buf[sz], *b = buf, *e = buf + sz;
    uc a[40], *p = a;
    inline void mflush() {
        std::cout.write(buf, b - buf);
        b = buf;
    }
    inline void putch(uc c) {
        if (b == e)
            mflush();
        *b++ = static_cast<char>(c);
    }
    inline void write(char c) {
        putch(static_cast<uc>(c));
    }
    inline void write(uc c) {
        putch(c);
    }
    template <typename T>
    inline std::enable_if_t<std::is_unsigned<T>::value &&
                            !std::is_same<T, uc>::value>
    write(T r) {
        if (!r) {
            putch('0');
            return;
        }
        while (r) {
            *++p = static_cast<uc>((r % 10) | 48);
            r /= 10;
        }
        while (p != a)
            putch(*p--);
    }
    template <typename T>
    inline std::enable_if_t<std::is_signed<T>::value &&
                            !std::is_same<T, char>::value>
    write(T r) {
        if (r < 0) {
            putch('-');
            r = ~(r - 1);
        }
        write(std::make_unsigned_t<T>(r));
    }
    inline void write(const char* s) {
        while (*s)
            putch(static_cast<uc>(*s++));
    }
    inline void write(const std::string& s) {
        for (char c : s)
            putch(static_cast<uc>(c));
    }
    template <typename... Args>
    inline std::enable_if_t<(sizeof...(Args) > 1)> write(Args&&... args) {
        (write(args), ...);
    }
    struct auto_flush {
        ~auto_flush() {
            mflush();
        }
    } auto_flush_;
} // namespace fast_o_
#undef my_isdigit
#undef my_isspace
#undef FASTIO_NO_PUNC
#undef FASTIO_NO_ALPHA
using fast_i_::read;
using fast_o_::write;
// fastio end.
// Kazusa begin.
#include <vector>
#include <numeric>
struct Kazusa {
    std::vector<ui> f, s, d;
    Kazusa() = default;
    Kazusa(ui n) : f(n), s(n, 1) {
        std::iota(f.begin(), f.end(), 0U);
    }
    ui fd(ui k) {
        while (k != f[k]) {
            k = f[k];
        }
        return k;
    }
    bool merge(ui u, ui v) {
        u = fd(u);
        v = fd(v);
        if (u == v) {
            return false;
        }
        if (s[u] > s[v]) {
            std::swap(u, v);
        }
        f[u] = v;
        s[v] += s[u];
        d.emplace_back(u);
        return true;
    }
    void quash() {
        ui u = d.back();
        d.pop_back();
        ui v = f[u];
        f[u] = u;
        s[v] -= s[u];
    }
};
// Kazusa end.

using namespace std;
using namespace literals;

static void test_case(ui ca [[maybe_unused]]) {
    ui n, m, k, q;
    read(n, m, k, q);
    vector<pair<ui, ui>> edges(m);
    for (ui i = 0; i < m; ++i) {
        read(edges[i].first, edges[i].second);
        --edges[i].first;
        --edges[i].second;
    }
    using TIII = tuple<ui, ui, ui>;
    vector<TIII> querys(q);
    vector<ui> las(m, nlim<ui>::max());
    for (ui i = 0; i < q; ++i) {
        ui e, c;
        read(e, c);
        --e;
        --c;
        if (las[e] != nlim<ui>::max()) {
            get<2>(querys[las[e]]) = i;
        }
        las[e] = i;
        querys[i] = TIII(e, c, q);
    }
    vector<vector<TIII>> ops(q * 4); // connect <0> and <1> with color <2>
    auto add_op = [&](this auto&& self, ui x, ui y, const TIII& va, ui u, ui l,
                      ui r) -> void {
        if (r <= x || y <= l) {
            return;
        }
        if (x <= l && r <= y) {
            ops[u].push_back(va);
            return;
        }
        const ui mid = (l + r) >> 1;
        self(x, y, va, u << 1, l, mid);
        self(x, y, va, u << 1 | 1, mid, r);
    };
    vector<Kazusa> kazusa(k, n * 2);
    vector<ui> now_color(m, nlim<ui>::max());
    [&](this auto&& self, ui u, ui l, ui r) -> void {
        for (auto [x, y, c] : ops[u]) {
            lassert(kazusa[c].merge(x, y));
        }
        if (l + 1 == r) {
            auto [e, c, nex] = querys[l];
            if (kazusa[c].merge(edges[e].first, edges[e].second)) {
                write("YES\n");
                kazusa[c].quash();
                if (l + 1 < nex) {
                    add_op(l + 1, nex, TIII(edges[e].first, edges[e].second, c),
                           1, 0, q);
                }
                now_color[e] = c;
            } else {
                write("NO\n");
                if (l + 1 < nex && now_color[e] != nlim<ui>::max()) {
                    add_op(l + 1, nex,
                           TIII(edges[e].first, edges[e].second, now_color[e]),
                           1, 0, q);
                }
            }
        } else {
            const ui mid = (l + r) >> 1;
            self(u << 1, l, mid);
            self(u << 1 | 1, mid, r);
        }
        for (auto [x, y, c] : ops[u]) {
            kazusa[c].quash();
        }
    }(1, 0, q);
}
#define MULTI_TEST 0
// #define IO_FILE_NAME ""
// #define LOCAL_FILE_IO
int main(int, char**) {
    cin.tie(nullptr)->sync_with_stdio(false);
#if !defined(LOCAL) && defined(IO_FILE_NAME) && !defined(ONLINE_JUDGE)
    freopen(IO_FILE_NAME ".in", "r", stdin);
    freopen(IO_FILE_NAME ".out", "w", stdout);
#elif defined(LOCAL) && defined(LOCAL_FILE_IO) && !defined(CPH)
    lassert(freopen("in.txt", "r", stdin));
    lassert(freopen("out.txt", "w", stdout));
#endif
    ui t_ = 1;
#if MULTI_TEST
#ifdef HAVE_FAST_IO
    read(t_);
#else
    cin >> t_;
#endif
#endif
    for (ui ca = 1; ca <= t_; ++ca) {
        test_case(ca);
    }
}