Dòmino P36445


Statement
 

pdf   zip

thehtml

A causa de les normes de distanciament social, a la sala CFIS ja no es pot jugar al mus. Ara, el dòmino solitari s’ha posat de moda: donades n peces, s’han de posar totes en fila, de manera que dues peces adjacents comparteixin el número que les connecta.

Per exemple, amb [3 2], [4 0], [5 2], [4 3] i [1 5], una solució és [0 4][4 3][3 2][2 5][5 1]. Observeu que les peces es poden girar.

En Sergi hi està jugant i vol trobar la solució lexicogràficament més petita. El podeu ajudar?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb una n entre 1 i 105. Segueixen n parells [x y], amb xy, on x i y estan entre 0 i 104. No hi ha peces repetides.

Sortida

Per a cada cas, escriviu la solució més petita seguint el format dels exemples. Si no hi ha cap solució, indiqueu-ho.

Public test cases
  • Input

    1  10000 9999
    4  0 1  1 2  4 5  5 6
    3  0 1  0 2  0 3
    5  0 4  7 4  1 7  8 1  0 8
    11  0 2  4 2  3 2  3 4  4 6  4 8  8 6  3 5  8 5  3 0  3 8
    

    Output

    yes [9999 10000]
    no
    no
    yes [0 4][4 7][7 1][1 8][8 0]
    yes [2 0][0 3][3 2][2 4][4 3][3 5][5 8][8 4][4 6][6 8][8 3]
    
  • Information
    Author
    Max Balsells
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++