UOJ Logo Zijian Online Judge

ZOJ

#22. 展览会(exhibition)

统计

Au 国的 Au++ 公司研发出了一项新的黑科技——传送门,现在他们要在各大城市举行展览会!

Au 国的 $n$ 个城市呈线性排列(城市从 $1$ 到 $n$ 编号),即第 $i$ 个城市到第 $i + 1$ 个城市有一条互相通达的长度为 $1$ 的道路$(i < n)$,现在 Au++ 公司希望将一对(两个)传送门放到一个两个城市中,供国民观赏。

Au++ 提供了免费试用服务,即来参观的人可以选择进入传送门,瞬间到达另一个传送门所在的城市中去,当然,也可以选择不进入传送门。

现有 $m$ 个人要参加这次展览会,每个人有一个游览计划,可以表示成二元组 $(a, b)$,表示他从城市 $a$ 出发,去参观一次传送门(即要到达一个传送门,但可以选择不进入),然后到城市 $b$ 去。

$m$ 个人要参加这次展览会,请你帮 Au++ 公司决定把传送门放在哪两个城市,使得所有人走的路的总长度(即忽略参观的时间)最短。

注意:每个人的游览互不影响。

输入格式

第一行两个整数 $n$ 和 $m$。

接下来 $m$ 行,每行两个正整数 $a$ 和 $b$,描述一个人的游览计划。

输出格式

一个正整数,表示最短的总长度。

样例一

input

5 2
1 3
2 4

output

2

explanation

将传送门分别放在 $2$、$3$ 号城市即可。这样两个人都需要走 $1$ 的长度。

样例二

见样例数据下载

限制与约定

对于 $30\texttt{%}$ 的数据,$n,m \le 100$

对于 $60\texttt{%}$ 的数据,$n,m \le 2000$

对于另外 $20\texttt{%}$ 的数据,对于所有人有 $a = b$

对于 $100\texttt{%}$ 的数据,$3 \le n,m \le 10^6$,对于所有人有 $a,b \le n$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载