/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 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