← 返回题目列表

AtCoder · nadafes2022_day2_e

E. 哈密顿电路

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

配点 : 500 点

問題文

N 我有一个完整的顶点图。顶点 i 和顶点 连接 j 的边长为 从 \min(|A_i-A_j|,|B_i-B_j|) 。

頂点 1 开始,顶部 2 它们的编号最大为 N 分别 1 每次经过,顶点 对于返回到 1 的所有循环,计算循环长度的总和。 除以 998244353 求余数。

制約

  • 输入全部为整数。
  • 2 \le N \le 2 \times 10^5
  • -10^9 \le A_i,B_i \le 10^9(1 \le i \le N)

入力

输入是按以下格式从标准输入给出的。

N
A_1\ B_1
A_2\ B_2
\vdots
A_N\ B_N

出力

输出答案。


入力例 1

3
1 2
3 5
4 2

出力例 1

6

頂点 1、頂点 2、頂点 3、頂点 1 ,周期长度为 2+1+0=3 。

頂点 1、頂点 3、頂点 2、頂点 1 ,周期长度为 0+1+2=3 。

因此,答案是 不大于 6 。