配点: 200 点
問題文
垂直 N 方形,横向 N 有一个棋盘,由分成方格的方格组成。从上面 i 番目 (1 \leq i \leq N),从左起 j 番目 (1 \leq j \leq N) 正方形,正方形 (i, j) 。 在以任意顺序连接
板上: N-1 放置皇后,i 皇后是方形的 它位于 (r_i, c_i) 。
这里,当该板满足以下条件时,该板为 状况良好 。
- 无论你看棋盘上的哪一排45度方格,皇后都是 2 不超过一个。
另外,给定的板面为 状况良好 有保证。
对于该板, 添加皇后,同时保留状况良好 在保留的同时添加皇后 1 判断是否可以放置它们,如果可以,输出位置。
制約
- 所有输入均以整数形式给出
- 2 \leq N \leq 5{,}000
- 1 \leq r_i, c_i \leq N (1 \leq i \leq N - 1)
- 给定的板是 状况良好 是
入力
输入是按以下格式从标准输入给出的。
N
r_1 c_1
r_2 c_2
\vdots
r_{N-1} c_{N-1}
出力
质量 如果你可以在 (i, j) 中放置皇后,请按以下格式输出。如果有多个答案,则任何一个输出都将是正确答案。
i j
如果你无法将其放置在任何地方
无论通过 -1 。
输出
入力例 1
5 5 5 3 1 1 2 4 3
出力例 1
2 4
质量 如果你可以在 (2, 4) 的哪排45度垂直、水平或对角方格,都不会放置皇后。因此, 即使在(2, 4) 上放置了皇后之后 状况良好 被保留。

入力例 2
5 2 5 3 1 1 2 4 4
出力例 2
-1