题目描述

yummy 听说杭州电子科技大学的体育馆不仅有着酷似飞碟的造型，还曾是杭州亚运会击剑项目的比赛场馆，因此决定前去游览这个校园。

校园可以看作一张有 \(n\) 个结点 \(m\) 条有向边的图，每个结点 \(i\) 都在平面上有个坐标 \((x_i, y_i)\)。体育馆的位置为 \((0, 0)\)。

注意，由于校园中立交桥的存在，即使 \((x_i, y_i) = (x_j, y_j)\)，也不代表 yummy 可以从结点 \(i\) 不经过任何边直接到达结点 \(j\)。

yummy 初始在结点 \(1\)，并打算经过若干条边到达结点 \(k\) 和朋友会合。

为了多角度地欣赏体育馆，yummy 希望 \((0, 0)\) 落在他经过的所有结点构成的凸包内部（不含边界）。由于他还不清楚朋友的具体位置，你需要对于所有 \(k = 1, \ldots, n\) 计算 yummy 至少游览几条边，多次经过同一条边要重复计数。

输入格式

输入的第一行有两个正整数 \(n, m\) （\(4 \le n \le 4000\)， \(4 \le m \le 8000\)），表示结点数和单行道数。

之后有 \(n\) 行，其中第 \(i\) 有两个整数 \(x_i, y_i\) （\(|x_i|, |y_i| \le 10^9\)），表示结点 \(i\) 的横纵坐标。

之后有 \(m\) 行，其中第 \(i\) 行有两个整数 \(u_i, v_i\)，表示一条从 \(u_i\) 到 \(v_i\) 的有向边。

输出格式

对于每个 \(k = 1, 2, \ldots, n\)，输出一行一个整数，具体地：

• 如果存在一条从 \(1\) 到 \(k\) 的路径凸包严格包含 \((0, 0)\)，则输出最少经过的边数。
• 如果不存在，则输出 \(-1\)。

样例输入

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

样例输出

8
6
3
5
4
7
-1