← 返回题目列表

AtCoder · typical90_cj

088. 相似但不同的方式(★6)

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

配点: 6 点

問題文

N 张卡片,每张卡片上都有编号,编号直到 1 减去 N 。卡片 i 上有正整数 A_i 。
E869120 和 square1001 从这些卡牌中分别选择了 1 张以上的卡牌。
关于双方选择卡牌的方式,已知满足以下所有条件。

条件1 E869120 选择的卡片上写着的整数的总和,与 square1001 选择的卡片上写着的整数的总和相等
条件2 i = 1, 2, \cdots, Q 对应地,没有人同时选择了卡片 X_i 和卡片 Y_i 没有人选择了两者
条件3 两者选择的卡片集合不相同

请输出两者可能的卡片选择方式之一但是,请注意,也可能存在 E869120 和 square1001 都选择的卡片。

制約

  • 2 \leq N \leq 88
  • 0 \leq Q \leq \frac{N(N-1)}{2}
  • 1 \leq A_i
  • A_1 + A_2 + ... + A_N \leq 8888
  • 1 \leq X_i \lt Y_i \leq N
  • i \ne j 如果 (X_i,Y_i) \ne (X_j,Y_j)
  • 所有输入均为整数
  • 存在满足条件的卡片选择方式

入力

输入是按以下格式从标准输入给出的。

N Q
A_1 A_2 \cdots A_N
X_1 Y_1
X_2 Y_2
 \vdots 
X_Q Y_Q

出力

E869120 选择了卡片 (B_1, B_2, \cdots, B_x) [B_1 < B_2 < \cdots < B_x] ,square1001 选择了卡片 (C_1, C_2, \cdots, C_y) [C_1 < C_2 < \cdots < C_y] 时,按以下格式 4 行。 在

x
B_1 B_2 \cdots B_x
y
C_1 C_2 \cdots C_y

入力例 1

5 2
3 1 3 2 3
1 2
1 4

出力例 1

4
2 3 4 5
3
1 3 5

A_2 + A_3 + A_4 + A_5 = 9, A_1 + A_3 + A_5 = 9 表示,两者选择的卡片上写的整数总和相等。
由于满足所有其他条件,因此此输出是正确的。
另外,例如以下输出也会被视为正确答案。

2
1 3
2
1 5

入力例 2

10 10
2 5 7 8 11 10 1 88 86 50
1 2
1 3
1 4
1 5
1 6
5 10
6 10
2 3
9 10
7 8

出力例 2

2
6 7
1
5