3652. 乘法还原

单点时限: 2.0 sec

内存限制: 512 MB

“时间会缓和所有的悲伤,
当你的悲伤被安抚以后,
你就会因为认识过我而感到满足。”

你永远会是我的朋友。你会想和我一起笑。

时间是神奇的东西,让数学和你成为了永远的朋友。

你总在和数学玩耍,数学却总是想法设法地为难你。

昨天,你才和数学一起玩了表达式展开。现在数学就为难你,让你尝试因式分解。

数学想了两个序列,分别是 ,随后她用这两个序列构造了一个表达式 。她告诉你这个表达式的展开式,让你还原出这两个序列。

但数学和你是很好的朋友,为了避免让你感到困惑,她保证了她想出来的数列满足以下几点。所以你还原出来的答案也要满足以下几点。

  • 满足严格单调增,即
  • 也满足
  • 序列的长度必须小于等于 序列的长度,即
  • 如果 序列的字典序必须小于等于 序列的字典序。

输入格式

第一行一个数 ,表示展开的表达式的项数。

接下去 行,第 行两个数是 (,表示表达式展开式的第 项为 。展开式中的同类项不会被合并。

输入保证有解。

输出格式

第一行两个数 ,分别表示 表达式的项数和 表达式的项数。

接下去两行分别 个数,分别表示 以及

题目保证有解。如果有多解输出任意一解。

样例

Input
4
1 3
4 1
2 3
2 4
Output
2 2
1 2
3 4
Input
4
1 1
2 2
2 1
2 1
Output
2 2
1 2
1 2

25 人解决,41 人已尝试。

35 份提交通过,共有 300 份提交。

8.1 EMB 奖励。

创建: 1 年前.

修改: 1 年前.

最后提交: 7 月前.

来源: EOJ Monthly 2018.12

题目标签