P15624 [ICPC 2022 Jakarta R] Contingency Plan

You are working as a manager in The ICPC Company. In the company building, there are $N$ computers, numbered from $1$ to $N$. There are $N - 1$ cables, numbered from $1$ to $N - 1$, that connect all the computers into a single network. Cable $i$ connects computer $U_i$ and $V_i$. Through your research, there are $N - 1$ levels of disasters, numbered from $1$ to $N - 1$, that might happen in the future. In disaster level $x$, all cables $i$ such that $1 \leq i \leq x$ are damaged. Damaged cables cannot be used for a connection. As a manager, you want to create a contingency plan. In your contingency plan, there should be $N - 1$ backup cables, numbered from $1$ to $N - 1$. If an existing cable $i$ is damaged, then backup cable $i$ will be deployed to connect computer $A_i$ and $B_i$. If an existing cable $i$ is not damaged, then backup cable $i$ is not deployed and is not used for a connection. For each disaster level, the backup cables, together with the undamaged cables, must keep all the computers connected in a single network. Furthermore, for practical reasons, if a cable that connects computers $u$ and $v$ exists, then there should not be any backup cable that connects computers $u$ and $v$ in your contingency plan. Create a contingency plan that satisfies all the requirements, or determine if such a plan is impossible to create. If several contingency plans exist, choose any of them.

Input begins with an integer $N$ ($2 \leq N \leq 100\,000$) representing the number of computers. Each of the next $N - 1$ lines contains $2$ integers $U_i$ $V_i$ ($1 \leq U_i, V_i \leq N$) representing cable $i$. All the cables connect all the computers into a single network.

If a contingency plan is possible to create, then the output consists of $N - 1$ lines, representing your contingency plan that satisfies all the requirements. Each line contains $2$ integers $A_i$ $B_i$ ($1 \leq A_i, B_i \leq N$) representing backup cable $i$. If several contingency plans exist, output any of them. If a contingency plan is impossible to create, then output $-1$ in a single line.

#### Explanation for the sample input/output #1 The following is an illustration for this sample. The circles represent the computers, while the black line and red dashed lines represent existing cables and backup cables, respectively. Damaged cables are not shown in the illustration. :::align{center}  ::: #### Explanation for the sample input/output #2 There should be $2$ backup cables in the contingency plan. You can only have $1$ backup cable, which will connect computers $1$ and $3$. The remaining pairs are already connected by the current cables.