logo AlgoBeat OnlineJudge
登录 注册

#200056. [NOIP 2008 普及组] 排座椅

内存限制:125 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

上课的时候总会有一些同学和前后左右的人交头接耳,这是令小学班主任十分头疼的一件事情。不过,班主任小雪发现了一些有趣的现象,当同学们的座次确定下来之后,只有有限的 对同学上课时会交头接耳。

同学们在教室中坐成了 列,坐在第 行第 列的同学的位置是 ,为了方便同学们进出,在教室中设置了 条横向的通道, 条纵向的通道。

于是,聪明的小雪想到了一个办法,或许可以减少上课时学生交头接耳的问题:她打算重新摆放桌椅,改变同学们桌椅间通道的位置,因为如果一条通道隔开了 个会交头接耳的同学,那么他们就不会交头接耳了。

请你帮忙给小雪编写一个程序,给出最好的通道划分方案。在该方案下,上课时交头接耳的学生的对数最少。

输入格式

第一行,有 个用空格隔开的整数,分别是

接下来的 行,每行有 个用空格隔开的整数。第 行的 个整数 ,表示坐在位置 的两个同学会交头接耳(输入保证他们前后相邻或者左右相邻)。

输入数据保证最优方案的唯一性。

输出格式

共两行。
第一行包含 个整数 ,表示第 行和 行之间、第 行和 行之间、…、第 行和第 行之间要开辟通道,其中 ,每两个整数之间用空格隔开(行尾没有空格)。

第二行包含 个整数 ,表示第 列和 列之间、第 列和 列之间、…、第 列和第 列之间要开辟通道,其中,每两个整数之间用空格隔开(列尾没有空格)。

样例

样例输入 1

4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4

样例输出 1

2
2 4

数据范围与提示

上图中用符号*、※、+标出了 对会交头接耳的学生的位置,图中 条粗线的位置表示通道,图示的通道划分方案是唯一的最佳方案。

2008 年普及组第二题