#include #include #include class LiteralUnionFind { protected: std::vector root_of, size_of; uint_fast32_t group; constexpr uint_fast32_t retrieve_true_root_of(const uint_fast32_t index) noexcept { return root_of[index] == index ? index : root_of[index] = retrieve_true_root_of(root_of[index]); } public: constexpr LiteralUnionFind(const uint_fast32_t N) : root_of(N), size_of(N, 1), group(N) { for (uint_fast32_t i = 0; i != N; ++i) root_of[i] = i; } constexpr bool is_connected(const uint_fast32_t a, const uint_fast32_t b) noexcept { return retrieve_true_root_of(a) == retrieve_true_root_of(b); } constexpr bool merge(const uint_fast32_t a, const uint_fast32_t b) noexcept { if (retrieve_true_root_of(a) != retrieve_true_root_of(b)) { if (size_of_group_of(a) >= size_of_group_of(b)) { size_of[root_of[a]] += size_of[root_of[b]]; root_of[b] = root_of[root_of[b]] = root_of[a]; } else { size_of[root_of[b]] += size_of[root_of[a]]; root_of[a] = root_of[root_of[a]] = root_of[b]; } --group; return true; } else return false; } constexpr uint_fast32_t size_of_group_of(const uint_fast32_t index) noexcept { return size_of[retrieve_true_root_of(index)]; } constexpr uint_fast32_t groups() const noexcept { return group; } }; static inline constexpr std::vector solve(const uint_fast32_t N, const uint_fast32_t M, const uint_fast32_t Q, const std::vector& U, const std::vector& V, const std::vector& B) noexcept { std::vector is_available_edge(M + 1, true); is_available_edge[0] = false; for (uint_fast32_t i = 0; i != Q; ++i) is_available_edge[B[i]] = false; uint_fast64_t count_unconnected = (N * static_cast(N - 1)) >> 1; LiteralUnionFind luf(N + 1); for (uint_fast32_t i = 1; i <= M; ++i) if (is_available_edge[i] && !luf.is_connected(U[i], V[i])) count_unconnected -= static_cast(luf.size_of_group_of(U[i])) * luf.size_of_group_of(V[i]), luf.merge(U[i], V[i]); std::vector ans(Q); for (uint_fast32_t i = Q - 1; i != UINT_FAST32_MAX; --i) { ans[i] = count_unconnected; if (!luf.is_connected(U[B[i]], V[B[i]])) count_unconnected -= static_cast(luf.size_of_group_of(U[i])) * luf.size_of_group_of(V[i]), luf.merge(U[i], V[i]); } return ans; } static inline void output(const uint_fast32_t Q, const std::vector& ans) noexcept { for (uint_fast32_t i = 0; i != Q; ++i) std::cout << ans[i] << '\n'; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); uint_fast32_t N, M, Q, i; std::cin >> N >> M; std::vector U(M + 1), V(M + 1); for (i = 1; i <= M; ++i) std::cin >> U[i] >> V[i]; std::cin >> Q; std::vector B(Q); for (i = 0; i != Q; ++i) std::cin >> B[i]; output(Q, solve(N, M, Q, U, V, B)); return 0; }