← 返回题目列表

AtCoder · codequeen2023_final_b

B. N 皇后问题

中文机器翻译题面 查看原题

配点: 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