本题数据过水，有 $O(n^2)$ 和其他做法能跑过。

在此提供 $O(n^2)$ 的 过题记录。

另外一个时间复杂度 $O(\frac{n^2}{k})$，依然能通过本题。

同时我的提交中还存在数组开小，乱赋初值等情况，但均 AC。

这里提供一个hack数据的生成器：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	puts("500000 1");
	for(int i = 1;i < 500000;i++)
		printf("%d %d\n",i,i + 1);
	puts("500000 1");
}

Output

499998

这是输出这个答案的程序提交记录。

这是以上 3 份代码的云剪贴板，我在代码中加入了数组开小，乱赋初值处的注释。