题目描述

平面国很高兴地宣布：今年，世界一级方程式锦标赛将首次来到平面国，举办“平面国大奖赛”。

与许多其他城市一样，平面国无法为比赛修建一条专用赛道。因此，平面国决定封闭一部分普通道路和路口，将它们组成一条比赛赛道。由于你在去年的平面国奥运会中表现出色，因此受聘负责寻找一条合适的赛道。

封闭道路会给当地居民带来不便，因此你希望需要封闭的路口数量尽可能少。

你的任务是选择若干条道路，使它们首尾相接构成一个环形赛道，并使赛道经过的路口数量尽可能少。

请注意，虽然平面国的所有道路都是双向道路，但出于安全考虑，在比赛期间，赛道只能沿一个固定方向行驶。

输入格式

第一行包含两个整数 $n$ 和 $m$（$4 \le n \le 10^5$，$5 \le m \le 3\times 10^5$），分别表示平面国中的路口数量和道路数量。

接下来 $n$ 行，每行包含两个整数 $x$ 和 $y$（$0 \le x,y \le 10^9$）。第 $i$ 行给出第 $i$ 个路口在平面国地图上的坐标。任意两个路口的位置互不相同。

接下来 $m$ 行，每行包含两个整数 $a$ 和 $b$（$1 \le a,b \le n$，且 $a\ne b$），表示第 $a$ 个路口和第 $b$ 个路口之间有一条道路。任意两个路口之间至多有一条道路。

保证任意两条道路只可能在它们共同的端点处相交。

此外，保证地图上的每个路口都是真正的道路交叉口，即每个路口至少与三条道路相连。

输出格式

输出一个整数，表示赛道至少需要经过多少个路口。

样例 1

输入

4 6
0 0
3 0
0 3
1 1
1 2
1 3
1 4
2 3
2 4
3 4

输出

3

样例 2

输入

10 15
1 5
2 1
3 4
4 2
5 3
6 2
7 3
8 1
9 4
11 5
1 2
1 3
1 10
2 4
3 5
4 5
4 6
5 7
6 7
6 8
7 9
8 10
9 10
2 8
3 9

输出

4