74 lines
1.5 KiB
Java
74 lines
1.5 KiB
Java
package chelper;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.List;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import misc.SimpleSavingChelperSolution;
|
|
|
|
|
|
public class A extends SimpleSavingChelperSolution {
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
wrapSolve(testNumber, in, out);
|
|
}
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
int n = in.nextInt();
|
|
|
|
int[] l = new int[n];
|
|
int[] r = new int[n];
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
l[i] = in.nextInt() - 1;
|
|
r[i] = in.nextInt() - 1;
|
|
}
|
|
|
|
boolean[] visited = new boolean[n];
|
|
|
|
List<int[]> things = new ArrayList<>();
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
if (visited[i]) {
|
|
continue;
|
|
}
|
|
|
|
int[] t = dfs(i, n, l, r, visited);
|
|
things.add(t);
|
|
}
|
|
|
|
for (int i = 0; i < things.size() - 1; i++) {
|
|
int[] t1 = things.get(i);
|
|
int[] t2 = things.get(i + 1);
|
|
|
|
r[t1[1]] = t2[0];
|
|
l[t2[0]] = t1[1];
|
|
}
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
out.println((l[i] + 1) + " " + (r[i] + 1));
|
|
}
|
|
}
|
|
|
|
int[] dfs(int v, int n, int[] l, int[] r, boolean[] visited) {
|
|
visited[v] = true;
|
|
|
|
int leftmost = v;
|
|
int rightmost = v;
|
|
|
|
if (l[v] != -1 && !visited[l[v]]) {
|
|
int[] t = dfs(l[v], n, l, r, visited);
|
|
leftmost = t[0];
|
|
}
|
|
|
|
if (r[v] != -1 && !visited[r[v]]) {
|
|
int[] t = dfs(r[v], n, l, r, visited);
|
|
rightmost = t[1];
|
|
}
|
|
|
|
return new int[]{leftmost, rightmost};
|
|
}
|
|
}
|