Equal Subset Products P87148


Statement
 

pdf   zip

html

You are given n different fractions a1/b1, …, an/bn, with 1 ≤ ai, bi ≤ n. Find two subsets I, J ⊆ {1, …, n}, distinct and with no common elements, such that

 
∏
i ∈ I
 
ai
bi
   =  
 
∏
j ∈ J
 
aj
bj
 .

For instance, if the given fractions are 2/1, 5/3, 1/2, 1/4, 2/4 and 3/6, a possible solution is 3/6 · 1/2 = 1/4.

Input

Input consists of several cases, each with an n between 1 and 105, followed by the n fractions.

Output

For each case, if there is some solution, print any one in two lines, one for each side of the equality, with the number of terms followed by those terms in any order. Follow strictly the format of the sample output. If there is no solution, print just one line with the word NO.

Public test cases

  • Input

    6 2/1 5/3 1/2 1/4 2/4 3/6
3 1/2 3/2 3/1
1 1/1
4 1/4 2/3 4/1 4/2

    Output

    2 1/2 2/1
0
1 3/2
2 3/1 1/2
1 1/1
0
0
2 4/1 1/4
    • Information
    Author
    Félix Moreno
    Language
    English
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++