The Sum-XOR Dialogue

Represent all possible pairs as a bipartite multigraph.

Create a left vertex $S_s$ for every possible sum $s$, and a right vertex $Y_y$ for every possible XOR value $y$. For every possible pair $(a,b)$, add an edge between $S_{a+b}$ and $Y_{a\mathbin{\mathrm{xor}}b}$.

At the beginning of a day, the remaining edges are exactly the pairs consistent with every earlier statement. Dadas knows the pair exactly when the vertex for the observed sum has degree $1$. Mog knows the pair exactly when the vertex for the observed XOR has degree $1$.

Because the statements are simultaneous, all edges incident to a degree-$1$ vertex at the beginning of a day must be removed simultaneously. The answer is therefore the peeling round in which the actual edge is removed. An edge that remains in the graph's $2$-core forever has answer $-1$.

Assume $X\ge 10$. Let $P$ be the largest power of two not exceeding $X$.

The only sum vertices of initial degree $1$ correspond to the following four pairs:

• $(1,2)$ with sum $3$.
• $(1,3)$ with sum $4$.
• $(X-2,X)$ with sum $2X-2$.
• $(X-1,X)$ with sum $2X-1$.

The initial degree-$1$ XOR vertices are classified as follows.

• If $X=P$, every pair $(i,P)$ with $1\le i<P$ is unique.
• If $X=P+1$, only $(1,P)$ and $(1,P+1)$ are unique.
• Otherwise, there is no such pair.

For the proof, fix an XOR value $y$. If $y<P$, the highest bit is preserved. Since $P\ge 8$, every occurring XOR value has at least two representations inside the lower block.

If $y\ge P$, write $y=P+z$. Write the larger number as $P+t$. The smaller number must then be $t\mathbin{\mathrm{xor}}z$, where $0\le t\le X-P$. Only $t=z$ is invalid because it produces $0$.

• If $X-P=0$, there is only one possible $t$, so $(z,P)$ is unique.
• If $X-P=1$, exactly $z=0,1$ leave one valid pair, namely $(1,P+1)$ and $(1,P)$.
• If $X-P\ge 2$, at least two valid values remain after excluding at most one.

Checking the vertices that can lose degree in each round gives the following table.

When $X=P$, the first round removes every $(i,P)$. Consequently, only $(P-3,P-1)$ remains at sum $2P-4$, and only $(P-2,P-1)$ remains at sum $2P-3$. These two edges are removed on day $2$.

When $X=P+1$, after day $1$, only $(P-2,P)$ remains at XOR $2P-2$. After removing it, only $(P-3,P+1)$ remains at sum $2P-2$. After removing that edge, only $(P-4,P)$ remains at XOR $2P-4$.

After all edges listed in the table are removed, every sum or XOR vertex of positive degree has degree at least $2$. This follows by checking the constant number of boundary configurations and, elsewhere, constructing another pair with the same sum or another valid value of $t$ with the same XOR. The assumption $X\ge 10$ keeps all required values in range. Therefore, no further peeling occurs.

For $X\le 9$, the slack used above is insufficient and extra cascades may occur. There are at most $\binom{9}{2}=36$ edges, so we directly construct the graph and simulate the peeling rounds.

Finding $P$ takes $O(\log X)$ time per test case. The small simulation has constant size. The total time complexity is $O(T\log X)$ and the extra space complexity is $O(1)$.

Solution written by GPT5.6