配点: 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