Construct an Array (Hard Version)

The values themselves are mostly a decoy. What matters is arranging which endpoint dominates each sum.

This may smell like 2-SAT, but signs alone are not enough: for opposite signs, the larger magnitude decides whether the sum is negative. Instead of fighting that fact, we weaponize it.

1. Turn the restrictions into a colored graph

Create one vertex for every array position. A restriction on $(i,j)$ becomes an undirected edge, possibly a loop:

• color $1$: $a_i+a_j\ge 0$;
• color $2$: $a_i+a_j<0$.

The key numerical observation is

$$|x|>|y| \quad\Longrightarrow\quad \operatorname{sign}(x+y)=\operatorname{sign}(x).$$

Indeed, if $x>0$, then $x+y\ge x-|y|>0$; if $x<0$, then $x+y\le x+|y|<0$.

So if all absolute values are distinct, every non-loop edge is controlled by the endpoint with larger absolute value. We will use exactly the magnitudes $1,2,\ldots,n$.

2. Which vertex can get the largest magnitude?

Consider only the vertices not handled yet, and suppose we want to give some vertex $u$ the largest remaining absolute value $M$. Every other active vertex will eventually have magnitude below $M$, so $u$ controls every currently active edge incident to it.

There are only two safe cases:

• If $u$ has no active type-$2$ edge, assign $a_u=+M$. Every active edge incident to $u$ is type $1$, and its sum will be positive.
• If $u$ has no active type-$1$ edge, assign $a_u=-M$. Every active edge incident to $u$ is type $2$, and its sum will be negative.

If both colored degrees are zero, either sign works; we choose negative.

This gives a peeling process: repeatedly remove a vertex whose active incident edges omit at least one color. The first removed vertex receives magnitude $n$, the next receives $n-1$, and so on.

3. The algorithm

For each vertex $u$, maintain two active degrees:

$$d_1(u)=\text{number of active type-1 incidences},\qquad d_2(u)=\text{number of active type-2 incidences}.$$

Then:

1. Put every vertex satisfying $d_1(u)=0$ or $d_2(u)=0$ into a queue.
2. Pop a vertex $u$.
3. If $d_1(u)=0$, record sign $-1$. Otherwise record sign $+1$; because $u$ was eligible and degrees only decrease, $d_2(u)=0$ must hold.
4. Remove $u$ from the active graph. For every incident edge $(u,v)$ of color $c$, decrement $d_c(v)$.
5. If this makes either colored degree of $v$ zero, enqueue $v$ if it has not already been enqueued.
6. If all vertices are removed, construct the array. Otherwise output NO.

Suppose the resulting removal order is

$$v_1,v_2,\ldots,v_n$$

and the recorded sign of $v_k$ is $s_k\in\{-1,+1\}$. Set

$$a_{v_k}=s_k(n-k+1).$$

Thus earlier removed vertices get strictly larger magnitudes.

A vertex already waiting in the queue is still considered active until it is popped. We keep updating its degrees, then choose its sign using the degrees it has at the actual pop time. This small implementation detail avoids hand-wavy nonsense around two queued adjacent vertices.

4. Why every produced array is valid

Take a non-loop restricted pair $(u,v)$, and suppose $u$ was removed before $v$. At the moment $u$ was removed, $v$ was still active, so this edge was counted in the appropriate colored degree of $u$.

Also,

$$|a_u|>|a_v|,$$

because earlier removal means larger assigned magnitude.

• If $(u,v)$ is type $1$, then $d_1(u)>0$ at that moment. Therefore $u$ could not have been removed using the rule $d_1(u)=0$; it must have had $d_2(u)=0$, so we recorded $a_u>0$. Since $u$ dominates the sum, $a_u+a_v>0$, which certainly satisfies $a_u+a_v\ge 0$.
• If $(u,v)$ is type $2$, the symmetric argument gives $a_u<0$. Since $u$ dominates, $a_u+a_v<0$.

For a loop $(u,u)$, its color contributes a positive degree while $u$ is active. A type-$1$ loop therefore forces the positive-sign rule, giving $2a_u>0$; a type-$2$ loop forces the negative-sign rule, giving $2a_u<0$.

Hence every restriction is satisfied.

5. Why getting stuck really means impossible

The nontrivial part is proving that the peeling process does not reject a solvable instance.

Suppose it gets stuck with a nonempty active set $S$. Then every vertex in $S$ has at least one active edge of each color. Assume, for contradiction, that some values satisfy all restrictions inside $S$.

Choose $x\in S$ maximizing $|a_x|$.

Case 1: $a_x\ge 0$

Vertex $x$ has a type-$2$ edge to some $y\in S$, so

$$a_x+a_y<0 \quad\Longrightarrow\quad a_y<-a_x\le 0.$$

Thus $|a_y|>|a_x|$, contradicting the choice of $x$. If this edge is a loop, the inequality is already impossible.

Case 2: $a_x<0$

Vertex $x$ has a type-$1$ edge to some $y\in S$, so

$$a_x+a_y\ge 0 \quad\Longrightarrow\quad a_y\ge -a_x>0.$$

Therefore $|a_y|\ge |a_x|$. Maximality forces equality. Now $y$ also belongs to the stuck residual graph, so it has a type-$2$ edge to some $z\in S$. Consequently,

$$a_z<-a_y<0,$$

which gives $|a_z|>|a_y|=|a_x|$, again a contradiction. Loops only make the contradiction arrive faster.

So a stuck residual graph cannot have any valid assignment. Therefore the algorithm outputs NO exactly when it should.

6. Implementation details

Each restriction is stored in both adjacency lists. For a loop, this creates two incidences and increments the degree twice; that is perfectly consistent, since we only care whether a colored degree is zero, and both incidences are removed together.

A boolean array ensures each vertex enters the queue once. Every stored incidence is traversed once, so there is no hidden quadratic disaster lurking in the bushes.

The constructed magnitudes are at most $n\le 2\cdot 10^5$, comfortably below $10^9$.

Complexity

For each test case, the time complexity is $O(n+m)$ and the memory complexity is $O(n+m)$.