Choose Your Queries
Contest: Educational Codeforces Round 170 (Rated for Div. 2)
Difficulty rating: 2700
Tags: constructive algorithms, dfs and similar, dp, graphs, greedy, trees

You are given an array $$$a$$$, consisting of $$$n$$$ integers (numbered from $$$1$$$ to $$$n$$$). Initially, they are all zeroes.

You have to process $$$q$$$ queries. The $$$i$$$-th query consists of two different integers $$$x_i$$$ and $$$y_i$$$. During the $$$i$$$-th query, you have to choose an integer $$$p$$$ (which is either $$$x_i$$$ or $$$y_i$$$) and an integer $$$d$$$ (which is either $$$1$$$ or $$$-1$$$), and assign $$$a_p = a_p + d$$$.

After each query, every element of $$$a$$$ should be a non-negative integer.

Process all queries in such a way that the sum of all elements of $$$a$$$ after the last query is the minimum possible.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 3 \cdot 10^5$$$; $$$1 \le q \le 3 \cdot 10^5$$$) — the number of elements in $$$a$$$ and the number of queries, respectively.

Then $$$q$$$ lines follow. The $$$i$$$-th of these lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) — the description of the $$$i$$$-th query.

Output format:
For each query, print a line containing two characters:

- the first character should be x if you choose $$$p=x_i$$$, or y if you choose $$$p=y_i$$$;
- the second character should be + if you choose $$$d=1$$$, or - if you choose $$$d=-1$$$.

If there are multiple answers, print any of them.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
3 4
1 2
3 2
3 1
1 2

Example output:
y+
x+
x-
y-

Example input:
4 4
1 2
2 3
3 4
3 2

Example output:
y+
y+
x-
y-

Editorial:
We will use the classical method for solving maximization/minimization problems: we will come up with an estimate for the answer and try to achieve it constructively.
The first idea. Since we have $$$n$$$ objects connected by binary relations, we can model the problem as a graph. Let the $$$n$$$ elements of the array be the vertices, and the $$$q$$$ queries be the edges. For each query, we would like to choose the direction of the edge (let the edge be directed towards the vertex to which the operation is applied) and the sign of the operation.
It would be great if, in each connected component, we could choose an equal number of pluses and minuses so that the sum equals zero. Or, if the number of edges in the component is odd, to make the sum equal to one. Obviously, it is not possible to do less than this.
It turns out that this is always possible. There is a well-known graph problem: to split the edges of an undirected connected graph into pairs with at least one common endpoint. We will reduce our problem to this one. If we split the graph into pairs, we will construct the answer from them as follows: we will direct the edges of each pair towards any common vertex, write + on the edge with the smaller number (query index), and write - on the edge with the larger number. This construction guarantees that each pair will not add anything to the sum, and each element will be non-negative after each query.
The problem of splitting into pair can be solved using the following algorithm. We will perform a DFS from any vertex and construct a DFS tree. Now we will divide the edges into pairs in the order from the leaves to the root. Let us stand at some vertex $$$v$$$. First, run the algorithm recursively for the children of $$$v$$$. When we finish processing the children, we will consider the following edges from the current vertex $$$v$$$: tree edges to the children, the edge to the parent, and back edges with the lower endpoint at $$$v$$$. Now, we form as many pairs as possible from the edges to the children and the back edges. We will remove all such edges from the graph. If their total number was odd, then one edge remains unpaired. Form a pair from it and the edge to the parent, and again remove them from the graph. It turns out that when we exit the recursive call, either there will be no edges left in the subtree at all, or there will be one tree edge that will be processed by the parent later. If the number of edges in the component is odd, then at the end, one edge without a pair will remain at the root.
I would also like to mention the following implementation details. In the adjacency list, it is better to store the indices of the queries rather than the vertices, and then derive the vertex numbers from them. This will allow for careful handling of multiple edges. Removing edges from the graph directly is also not very convenient. The most convenient way to work around this, in my opinion, is to maintain an array that marks that the edge with such a query number is now removed. Alternatively, for back edges, we can check whether $$$v$$$ is the upper or lower endpoint, as well as return a flag from the depth-first search indicating "is the edge to the child removed".
Overall complexity: $$$O(n + q)$$$.