/*
реализовать структуру со следующими интерфейсами

add(x): добавить x в структуру
getUnique(): вернуть какой-нибудь элемент, встречающийся в структуре ровно один раз, или null, если таких нет
erase(x): удалить ровно одно вхождение элемента x, если такой есть
*/


template <typename T>
class GetUniqueSet
{
public:
    GetUniqueSet() {}

    void Add(T t)
    {
        Data.insert(t);
        int count = (Counters[t] += 1);

        if (count == 1)
            UniqueElems.insert(t);
        else if (count == 2)
            UniqueElems.erase(t);
    }

    std::optional<T> GetUnique() const
    {
        if (UniqueElems.empty())
            return {};

        return *(UniqueElems.begin());
    }

    void Erase(T t)
    {
        auto it = Data.find(t);

        if (it == Data.end())
            return;

        Data.erase(it);
        int count = (Counters[t] -= 1);

        if (count == 1)
            UniqueElems.insert(t);
        else if (count == 0)
        {
            UniqueElems.erase(t);
            Counters.erase(t);
        }
    }

private:
    std::unordered_multiset<T> Data;
    std::unordered_map<T, int> Counters;
    std::unordered_set<T> UniqueElems;
};