Espressioni senza operatori

Un’espressione senza operatori (ESO) contiene coppie annidate di parentesi tonde () oppure quadre [] e sequenze di numeri; inoltre, una ESO inizia sempre con la tonda aperta e termina sempre con la tonda chiusa: tale coppia di parentesi racchiude l’intera espressione.

Per esempio, la seguente e’ una ESO: ( 58 [ 65 84 ( 47 ) 29 81 [ ( 18 21 ) 91 72 ] 45 ] 19 12 34 15 ).

L’ordine degli elementi immediamente contenuti in una coppia di parentesi (cioè interi o altre coppie di parentesi annidate con tutto ciò contenuto in esse) può essere cambiato con le seguenti regole, dove a, b, c, d, …, sono numeri oppure coppie di parentesi che contengono sottoespressioni:

• l’espressione ( a b c d …) può essere permutata in un qualunque ordine, per esempio ( c d b a …);
• l’espressione [ a b c d …] può rimanere con l’ordine corrente [ a b c d …] oppure può essere ribaltata in [… d c b a ].

Due ESO sono equivalenti se contengono gli stessi elementi e possono essere trasformate l’una nell’altra utilizzando le due regole suddette.

Per esempio, la ESO ( 15 19 34 [ 45 [ ( 21 18 ) 91 72 ] 81 29 ( 47 ) 84 65 ] 12 58 ) è equivalente a quella elencata sopra perché possiamo ottenerla con la seguente trasformazione:

•  Il primo passo trasforma
  ( 15 19 34 [ 45 [ ( 21 18 ) 91 72 ] 81 29 ( 47 ) 84 65 ] 12 58 )
  in ( 58 [ 45 [ (21 18 ) 91 72 ] 81 29 ( 47 ) 84 65 ] 19 12 34 15 ):
  applichiamo la regola 1 trasformando ( a b c d e f ) in ( f d b e c a ),
  dove a = 15, b = 19, c = 34, d = [ 45 … 65], e = 12, f = 58.
• Il secondo passo trasforma
  ( 58 [ 45 [ ( 21 18 ) 91 72 ] 81 29 ( 47 ) 84 65 ] 19 12 34 15 )
  in ( 58 [ 65 84 ( 47 ) 29 81 [ ( 21 18 ) 91 72 ] 45 ] 19 12 34 15 ):
  applichiamo la regola 2 trasformando [a b c d e f g ] in [ g f e d c b a ],
  dove a = 45, b = [ ( 21 18 ) 91 72 ], c = 81, d = 29, e = ( 47 ), f = 84, g = 65.
• Il terzo passo trasforma
  ( 58 [ 65 84 ( 47 ) 29 81 [ ( 21 18 ) 91 72 ] 45 ] 19 12 34 15 )
  in ( 58 [ 65 84 (47 ) 29 81 [ ( 18 21 ) 91 72 ] 45 ] 19 12 34 15 ):
  applichiamo la regola 1 trasformando (a b) in (b a),
  dove a = 21, b = 18.

Date N ESO della stessa lunghezza, il tuo compito è di dividerle in gruppi tali che, prese due qualunque ESO in uno stesso gruppo, queste sono equivalenti, mentre non lo sono se sono prese da due gruppi diversi.
Notare che un gruppo può essere costituito da una sola ESO nel caso che quest’ultima non sia equivalente a nessun’altra.

Dati in Input

Il file input.txt è composto da N+1 righe.

• La prima riga contiene due interi N e M separati da uno spazio, che rappresentano rispettivamente il numero di ESO e la lunghezza di ciascuna di esse (ossia quanti interi e quante parentesi contiene).
• La I-esima delle rimanenti N righe rappresenta la I-esima ESO: per facilitarne la lettura dell’input, i numeri sono sempre positivi, la parentesi tonda aperta è codificata dall’intero -1, quella chiusa dall’intero -2, la parentesi quadra aperta è codificata dall’intero -3 e quella chiusa dall’intero -4; in questo modo è sufficiente leggere una ESO come una sequenza di M interi separati da uno spazio, dove i numeri negativi rappresentano le parentesi.

Dati in Output

Il file output.txt è composto da G+1 righe.

• La prima riga contiene il numero G di gruppi trovati.
• Ciascuna delle G righe successive, rappresenta un gruppo e contiene interi separati da uno spazio: il primo intero è il numero E di elementi nel gruppo, e gli altri rappresentano le E ESO che appartengono al gruppo, dove la I-esima ESO dell’input è rappresentata dall’intero positivo I nell’output.

Assunzioni

• 1 <= N <= 1000
• 1 <= M <= 1000
• 1 <= G <= 1000
• Una ESO contiene al massimo 1000 interi (inclusi i negativi per le parentesi).

Esempi

Note

• Quando due ESO contengono numeri diversi, chiaramente non possono essere equivalenti.
• All’interno di una ESO non ci sono due numeri positivi uguali e non ci sono coppie di parentesi vuote, ovvero () oppure [], senza alcun elemento interno.