3652. 乘法还原

单点时限: 2.0 sec

内存限制: 512 MB

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

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

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

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

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

数学想了两个序列,分别是 ${a_i }$ 和 ${ b_i }$,随后她用这两个序列构造了一个表达式 $(x_{a_1} + \cdots + x_{a_m}) \cdot (x_{b_1} + \cdots + x_{b_n})$。她告诉你这个表达式的展开式,让你还原出这两个序列。

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

  • ${ a_i }$ 满足严格单调增,即 $a_1 < a_2 < \cdots < a_m$。
  • ${ b_i }$ 也满足 $b_1 < b_2 < \cdots < b_n$。
  • $a$ 序列的长度必须小于等于 $b$ 序列的长度,即 $m \le n$。
  • 如果 $m = n$,$a$ 序列的字典序必须小于等于 $b$ 序列的字典序。

输入格式

第一行一个数 $n$ $(1\le n\le 10^{5})$ ,表示展开的表达式的项数。

接下去 $n$ 行,第 $k$ 行两个数是 $i_k,j_k$ ($1\le i_k, j_k \le 10^{9})$,表示表达式展开式的第 $k$ 项为 $x_{i_k} x_{j_k}$。展开式中的同类项不会被合并。

输入保证有解。

输出格式

第一行两个数 $m,n$,分别表示 $a$ 表达式的项数和 $b$ 表达式的项数。

接下去两行分别 $m, n$ 个数,分别表示 $a_1,a_2,\ldots,a_m$ 以及 $b_1,b_2,\ldots,b_n$ 。

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

样例

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

27 人解决,44 人已尝试。

37 份提交通过,共有 310 份提交。

5.6 EMB 奖励。

创建: 6 年,1 月前.

修改: 6 年前.

最后提交: 1 年,1 月前.

来源: EOJ Monthly 2018.12

题目标签