Auto comment: topic has been updated by -is-this-dp (previous revision, new revision, compare).

I believe it is solvable using this method: Store a vector of all pairs in a vector called pairs. Also, store a prefix array called pref (ie pref[i] = hash(pairs[0]) ^ hash(pairs[1]) ^ ... ^ hash(pairs[i])). We would also need a map of prefix hashes for every element called prefmap. For every operation of type 1, we would add the pair to pairs, and add prefmap[x].back() ^ hash({x, y}) to prefmap[x] and prefmap[y].back() ^ hash({x, y}) to prefmap[y]. Note that you would only add one copy of (x, y) if x == y. For every operation of type 2, we will check if prefmap[v].size() == pairs.size(), if so, print -1. If the sizes are different, then we can binary search for the first value where the two arrays differ. If there can be duplicate pairs of {x, y}, then you can either use hash({x, y, i}) instead of hash({x, y}) or add the hashes together and mod. I'm not sure if I explained my approach clearly, but I hope this satisfies your question.

This solution is very stupid but it should work: store your pairs are $$$y[x] = {\text{uncompressed y values}}$$$. Now, for each query, realise that if we even have a single $$$x$$$ such that $$$x\neq v$$$ and $$$y[x].\text{size}() \gt 1$$$, we're done. You can find such an $$$x$$$ with a walk on a fenwick tree.

How many $$$v$$$ values can not satisfy this 'hack'? The answer is: exactly $$$1$$$! The reason this is true is because as soon as we add a duplicate $$$x$$$ to $$$\ge 2$$$ positions, every future query becomes 'free'. So we can maintain additional information and solve naively for just that singular $$$v$$$.

The other possibility is that we keep adding points at distinct x positions. In this case, to answer a query, we do the exact same process but on $$$x[y]$$$ instead of $$$y[x]$$$. Notice that, since points are distinct, we will only have to perform $$$2$$$ checks.

This can be solved very funny using Segment Tree.

Let create vector<vector<pair>> answer(N) — which maintain answers for each $$$v$$$.

For each pair $$$(x, y)$$$ we push_back it to all answer[v] where $$$v \ne x \text{ and }v \ne y$$$.

Using Segment Tree we can optimize this to $$$O(\ln N)$$$ for operation.

(Sorry if it's already solved, I didn't catch other solutions)

there are at most 2 possible v's for which the answer is -1 at any point.
if the answer isn't -1, there will always be 2 pairs 'a' and 'b' such that the answer is either 'a' or 'b' for all possible v's
store all the above and the problem is solved

The simplest way I can think of is to view it as a graph.

1.If at any point we have two separate components, the answer can be obtained from one of any pair of nodes from different 2 components.(maximum of 2 matchings per query also same for all future query ) just use 2 pairs again and again

2.if all nodes are in a single connected component and two nodes have more than two children, we can find the answer from those two triplets (for example, 1 ↔ 2 ↔ 3 and 1 ↔ 3 ↔ 4). (maximum of 4 matchings per query)

Otherwise, just choose any two different pairs of nodes and try to match them (this means all nodes are in the same component and share a common connection). If no match is possible, the answer is -1.

So the time complexity is just O(q)

you can store in pairs in the from of $$$(x, y, swapped)$$$ where $$$x \lt y$$$ and $$$swapped$$$ is a bool variable
then one of first or last pair will be your answer, if both are not not valid such pair don't exist.

Easy solution for this problem:

You can keep track of pairs by their indices, and you can actually store the index of a good pair for every $$$v$$$. Let's use a map that stores the index of the good pair, and if there are many of them, just keep the one with the minimum index.

Now, if you add a pair $$$(x, y)$$$, updating the map is very easy:

if map[x] == i:
  map[x]++

if map[y] == i:
  map[y]++

If $$$map[v] \gt i$$$, where $$$i$$$ is the index of the last added pair, then the answer for $$$v$$$ is $$$-1$$$.

Why does this work? Because in $$$map[v]$$$ you actually keep the MEX of the indices of bad pairs. The MEX is the first good pair, and if such an index doesn’t exist, then the MEX will be greater than $$$i$$$.

My thought:

Firstly, ignore duplicate additions (for the purposes of this, two coordinates are duplicates if the contain the same values, but order doesn't matter) and replace all pairs initially in the multiset with addition queries, so you start with an empty multiset

Once there are 2 distinct values in the multiset, we can do the following process

a) If both contain no shared values, we can simply ignore all future additions as it's guaranteed that one of those two will work b) If they share some value v, the only value that we output -1 for is v, so we can ignore all future additions that also contain the value v, and as soon as we have a pair that doesn't contain v, we can ignore all addition queries.

Since the maximum size of the multiset is 3 with this strategy, we can simply iterate through the multiset during each query.

(judging from the complexity of the other solutions, I might be missing something, apologies if I am)

Whenever you have two pairs with set{x,y} != set{x2,y2}, the answer will always be one of those pairs. Otherwise we know all pairs (or points) lie on some vertical or horizontal line. If v = the coordinate of that line return -1. otherwise upper bound on v and check if it exists or not. Do the same for last element < v.

Very simple solution: use a naive approach, but keep at most 3 pairs in the multiset: first pair $$$p$$$, first pair that not contains p.x and first pair that not contains p.y.