← 返回题目列表

Codeforces · 28/A

A. 本德问题

中文机器翻译题面 查看原题

Robot Bender 决定将 Fray 作为生日礼物。他钉了 n 个钉子,并按某种顺序从 1 到 n 编号。本德决定用金属棒制作一幅画。图片是一条封闭的折线,其顶点应该是钉子(按给定的顺序)。折线的线段应与坐标轴平行。折线允许有自相交。 Bender 可以拿起一根杆,在任何地方精确地折叠一次,形成 90 度角。然后,他可以将折叠的位置固定到一些空闲的钉子上,并将该杆的两端固定到相邻的钉子上。如果钉子上没有连接杆(无论是在其末端还是在折叠处),则认为钉子未被占用。任何杆都不能使用两次。不需要使用所有的杆。

帮助本德解决这项艰巨的任务。

输入

第一行包含两个正整数n和m(4≤n≤500,2≤m≤500,n为偶数)——钉子的数量和棒的数量。接下来n行中的第i行包含一对整数,表示第i个指甲的坐标。钉子的连接顺序应与输入中给出的顺序相同。最后一行包含 m 个整数——棒的长度。所有坐标的绝对值不超过 104。棒的长度在 1 到 200 000 之间。任何棒都不能使用两次。保证给定折线的所有线段都平行于坐标轴。没有三个连续的钉子位于同一条线上。

输出

如果无法解决Bender问题,则输出NO。否则,第一行输出YES,第二行输出n个数字——其中第i个应该是第i个钉子上附着的杆的数量,如果没有这样的杆,则输出-1。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

4 2
0 0
0 2
2 2
2 0
4 4

输出 #1

YES
1 -1 2 -1

输入 #2

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

输出 #2

YES
1 -1 2 -1 3 -1

输入 #3

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

输出 #3

NO