#P18635. Interval Problem
Interval Problem
Interval Problem
给定 个区间 。将每个区间视为一个顶点;若两个区间相交,就在对应顶点之间连一条无向、无权边。
令 表示第 个区间对应的顶点到第 个区间对应的顶点的最短路长度。如果两点之间不存在路径,定义 。自身到自身的距离也为0。
对于 ,分别计算
输入格式
第一行一个整数 。
随后 行,第 行两个整数 。
输出格式
输出 行,第 行表示原输入中第 个区间的距离和。
数据范围
,。保证所有区间的全部 个端点互不相同。
样例输入 1
5
2 3
6 7
1 9
5 10
4 8
样例输出 1
7
5
4
5
5