Euler tour
Contest: Codeforces Round 512 (Div. 1, based on Technocup 2019 Elimination Round 1)
Difficulty rating: 3500
Tags: constructive algorithms, trees

Euler is a little, cute squirrel. When the autumn comes, he collects some reserves for winter. The interesting fact is that Euler likes to collect acorns in a specific way. A tree can be described as $$$n$$$ acorns connected by $$$n - 1$$$ branches, such that there is exactly one way between each pair of acorns. Let's enumerate the acorns from $$$1$$$ to $$$n$$$.

The squirrel chooses one acorn (not necessary with number $$$1$$$) as a start, and visits them in a way called "Euler tour" (see notes), collecting each acorn when he visits it for the last time.

Today morning Kate was observing Euler. She took a sheet of paper and wrote down consecutive indices of acorns on his path. Unfortunately, during her way to home it started raining and some of numbers became illegible. Now the girl is very sad, because she has to present the observations to her teacher.

"Maybe if I guess the lacking numbers, I'll be able to do it!" she thought. Help her and restore any valid Euler tour of some tree or tell that she must have made a mistake.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$), denoting the number of acorns in the tree.

The second line contains $$$2n - 1$$$ integers $$$a_1, a_2, \ldots, a_{2n-1}$$$ ($$$0 \leq a_i \leq n$$$) — the Euler tour of the tree that Kate wrote down. $$$0$$$ means an illegible number, which has to be guessed.

Output format:
If there is no Euler tour satisfying the given description, output "no" in the first line.

Otherwise, on the first line output "yes", and then in the second line print the Euler tour which satisfy the given description.

Any valid Euler tour will be accepted, since the teacher doesn't know how exactly the initial tree looks.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
An Euler tour of a tree with $$$n$$$ acorns is a sequence of $$$2n - 1$$$ indices of acorns. such that each acorn occurs at least once, the first and the last acorns are same and each two consecutive acorns are directly connected with a branch.

Example input:
2
1 0 0

Example output:
yes
1 2 1

Example input:
4
1 0 3 2 0 0 0

Example output:
yes
1 4 3 2 3 4 1

Editorial:
First let's try to find some conditions whether it is possible to recover correct euler tour. Of course for every euler tour $$$a_i$$$ $$$\neq$$$ $$$a_{i+1}$$$ and $$$a_1$$$ $$$=$$$ $$$a_{2n-1}$$$ (because we start and finish in root). Moreover if there exist four index $$$i_1$$$ $$$<$$$ $$$i_2$$$ $$$<$$$ $$$i_3$$$ $$$<$$$ $$$i_4$$$ such that $$$a_{i_1}$$$ $$$=$$$ $$$a_{i_3}$$$ and $$$a_{i_2}$$$ $$$=$$$ $$$a_{i_4}$$$ and $$$a_{i_1}$$$ $$$\neq$$$ $$$a_{i_2}$$$ than answer is $$$NO$$$ (because vertex is an ancestor of another o there is no relation between them). There is one more tricky condition - parity of positions of all occurences of element $$$x$$$ is the same. Also, between two equal elements with distance $$$2k$$$ there can be at most $$$k$$$ distinct elements.
It turns out that those conditions are sufficient - we will prove it by constructing an answer.
So first let's observe that if we have to equal elements it means that there is subtree between them - we can solve it independently from the rest of a tree and then forget about this subtree. So as long as we have two equal elements $$$i$$$ $$$<$$$ $$$j$$$ than we can first solve euler tour between them and then delete elements $$$i+1,i+2...,j$$$. So now we want to solve euler tour where no element occur more than once. Let's say that this tour has length $$$2k-1$$$ then if we have less than $$$k$$$ elements we can replace any $$$0$$$ with any unused elements.
Now if there are three elements in a row with values $$$x,y,0$$$ or $$$0,y,x$$$ than we can replace them with $$$x,y,x$$$ and forget about it. If we get rid of all triplets like this than we have tour in form of $$$a_1,0,a_2,0,...,0,a_k$$$. It's easy to observe that we can replace every $$$0$$$ with our root (subtree's root). There is a special case when we don't have any root (if solving for whole tree), than we have to find any vertex which can be root and then solve our problem. Straightforward implementation will be $$$O(n^2)$$$ but it can be easily reduced to $$$O(nlogn)$$$ and it can be even reduced to $$$O(n)$$$, but $$$O(nlogn)$$$ was enough to be accepted.
More details about reducing $$$O(n^2)$$$ to $$$O(n)$$$ in code.