Subconjunts amb productes iguals P87148

Us donen n fraccions diferents a₁/b₁, …, a_n/b_n, amb 1 ≤ a_i, b_i ≤ n. Heu de trobar dos subconjunts I, J ⊆ {1, …, n}, diferents i sense elements comuns, tals que

Per exemple, si les fraccions donades són 2/1, 5/3, 1/2, 1/4, 2/4 and 3/6, una solució possible és 3/6 · 1/2 = 1/4.

Entrada

L’entrada consisteix en diversos casos, cadascun amb una n entre 1 i 10⁵, seguida de les n ‍fraccions.

Sortida

Per a cada cas, si hi ha solució, escriviu-ne qualsevol en dues línies, una per a cada banda de la igualtat, amb el nombre de termes seguit d’aquests termes en qualsevol ordre. Seguiu estrictament el format de l’exemple de sortida. Si no hi ha solució, escriviu una sola línia amb la paraula NO.