编程题
### 问题描述 小齐养了 $N$ 头奶牛,编号为 $1$ 到 $N$,它们构成了一个复杂的社交网络,每两头奶牛之间可能存在相互"哞"的关系,形成了一个奶牛社交网络。 每头奶牛位于农场的不同坐标 $(x, y)$ 上,我们知道有 $M$ 对奶牛之间存在"哞"的关系。如果两头奶牛相互"哞",则它们属于同一个奶牛社交网络。 为了升级农场,小齐想要修建一个矩形围栏,使得围栏的边与坐标轴平行。小齐希望确保至少有一个奶牛社交网络完全被围栏包围,即围栏的边界上的奶牛也算在被包围的奶牛社交网络中。请帮助小齐确定满足这一要求的围栏的最小可能周长。 ### 输入格式 第一行包含两个整数 $N$ 和 $M$。 接下来的 $N$ 行,每行包含一头奶牛的坐标 $(x, y)$,坐标为非负整数,且不超过 $10^8$。 接下来的 $M$ 行,每行包含两个整数 $a$ 和 $b$,表示存在"哞"关系的两头奶牛的编号。 ### 输出格式 输出一个整数,表示满足要求的围栏的最小周长。 ### 样例输入 ``` 7 5 0 5 10 5 5 0 5 10 6 7 8 6 8 4 1 2 2 3 3 4 5 6 7 6 ``` ### 样例输出 ``` 10 ``` ### 评测数据规模 $20 < N \leq 10^5$。
查看答案
赣ICP备20007335号-2