SP2658 WAR - Art of War

战国时期（公元前473年至公元前221年）是指春秋时期之后的动荡岁月。那时候，中国被分割成许多小国，彼此争斗不休。与之前强调骑士精神、以权力平衡或解决争端为目的的战争不同，战国时期的战争目标是征服及彻底消灭其他国家。最终，齐、楚、燕、韩、赵、魏和秦这七个国家崛起，被称为“七雄”。经过多次结盟与反结盟，秦国依次击败其他国家，结束了这一时期。 你有一张地图，显示各国首都的位置以及各国间的边界线段。你的任务是判断哪些国家是敌对关系。这很简单，如果两个国家有共同的边界，它们便是敌人。

输入包含若干组测试用例。每组测试用例首先是一行两个整数，表示国家数量 $1 \le n \le 600$ 和边界线段数量 $1 \le m \le 4000$。接下来的 $n$ 行，每行两个整数，表示每个国家首都的坐标。接下来的 $m$ 行，每行四个整数 $x_1, y_1, x_2, y_2$，表示一条从 $(x_1, y_1)$ 到 $(x_2, y_2)$ 的边界线段。（每条边界线段所分隔的国家没有明示，但可通过边界的走向推断。） 每个国家都由连续的边界线围成，并被无尽的荒野所包围。因此，边界线段不是分隔两个国家，就是分隔一个国家和荒野。不会出现一条边界线段两侧是同一国家，或者两侧都是荒野的情况。每个国家中只有一个首都，荒野中没有首都。边界线段不会相互交叉，只会在端点处相交。 输入以 $n = m = 0$ 的特殊情况结束。

对于每组测试用例，你需要输出 $n$ 行，每行描述该国家的敌人信息。如果两个国家有共同的边界线，它们就是敌人。输出的每一行以一个整数 $x$ 开头，表示该国家有 $x$ 个敌人。接下来是 $x$ 个整数，表示该国家的敌人编号。这些编号范围为 1 到 $n$，第一行输入的首都是编号为 1 的国家，以此类推。 **本翻译由 AI 自动生成**