UOJ Logo Universal Online Judge

UOJ

#389. 【UNR #3】白鸽

附件下载 统计

在咕了无数锅和 ddl 之后,S***pe 终于如愿以偿,变成了一只翱翔在天空中的白鸽。S***pe 很久以前听说过,白鸽的使命,就是以不同的方向飞过天空,带给地上的人们无尽的灵感。可是刚刚被变成白鸽的 S***pe 心理并不平衡,他远远地看见了地面上那个甩锅给他的人 w*x,他决定不给 w*x 提供应该提供的灵感,而且 S***pe相信不给灵感的方法就是绕着 w*x 顺时针转圈,这样的话对于 w*x 来说白鸽就只有往右侧飞行,而不能看到白鸽以不同的方向飞过天空了。

S***pe 觉得自己的行程必须经过若干个关键点,他请你帮他规划路线。

简而言之,现在在二维平面上,有一个给定一张 n 个点 m 条边的无向图作为线路,保证无自环。点从 1 开始编号。

在这张图上的每个节点都在二维平面上有自己的坐标,而一条边对应了连接这两个点的线段,S***pe 的目标是1 号点开始飞行,每次沿着一条线段到达一个新的点,循环往复最后停1 号点,且经过每条线段恰好一次。同时你需要最大化围绕原点顺时针旋转的次数。

顺时针旋转的次数:假设 w*x 在 S***pe 飞行的过程中始终保持正面朝向 S***pe,那么在 S***pe 结束飞行之后 w*x 原地右转的圈数就是顺时针旋转的次数(可以为负)。

如果无解输出 1。保证没有两个点重合,没有点和原点重合,且没有两个点所确定的直线经过原点。

输入格式

第一行两个正整数 n,m 分别表示这张无向图的点数和边数。

接下来 n 行每行两个整数 xi,yi 表示第 i 个点的坐标。

接下来 m 行每行两个整数 ui,vi 表示从点 ui 到点 vi 之间有一条无向边。

输出格式

一行一个整数,如果是 1 表示无解,否则表示最大的旋转次数。

样例一

input

5 10
1 9
6 -8
9 7
-5 -10
10 -6
1 3
3 4
2 3
1 4
5 2
4 5
1 3
3 1
4 1
3 1

output

2

explanation

样例中的图如下图所示,注意图中的重边未被标识。

样例一解释

一种最优的遍历顺序是:

13254134131

再次提醒:注意重边。

样例二

input

3 5
-764351767 899476675
103147230 -443149366
432530806 578822602
2 3
2 3
1 3
3 1
2 3

output

-1

explanation

不存在满足条件的路径。

样例三

见样例数据下载。

样例四

见样例数据下载。

限制与约定

对于所有数据,1n,m2×104|xi|,|yi|1091ui,vin,uivi

子任务分值限制
115n,m10
215n,m20
320n,m100
420n,m5000
530n,m2×104

时间限制1s

空间限制256MB

下载

样例数据下载