Sponsor e atleti

Alle Olimpiadi invernali, al pari di altre manifestazioni sportive internazionali, gli sponsor equipaggiano più di un atleta.
Per evitare che il messaggio pubblicitario arrivi al consumatore in modo confuso, un noto principio di marketing insegna che per ogni coppia di sponsor A e B deve occorrere uno solo dei seguenti due casi:

  • gli atleti ingaggiati dallo sponsor A e quelli ingaggiati dallo sponsor B sono completamente diversi e, quindi, formano due insiemi disgiunti;
  • gli atleti ingaggiati dallo sponsor A sono tutti ingaggiati anche dallo sponsor B o, viceversa, tutti gli atleti ingaggiati dallo sponsorB sono anche ingaggiati dallo sponsor A.

In altre parole, non deve mai accadere che esistano due sponsor A e B che contraddicano tale principio di marketing e, pertanto, verifichino simultaneamente tutte e tre le seguenti condizioni:

  1. vi sono degli atleti ingaggiati sia da A che da B,
  2. vi sono degli atleti ingaggiati da A ma non da B,
  3. vi sono degli atleti ingaggiati da B ma non da A.

Scrivete un programma che verifichi se N atleti ingaggiati da M sponsor rispettano il principio sopra indicato, supponendo che gli atleti siano numerati da 1 a N e che gli sponsor lo siano da 1 a M.

Dati in Input

Il file input.txt è composto da 1+N righe.
La prima riga contiene due interi positivi separati da uno spazio:

  • il primo intero rappresenta il numero N di atleti
  • e il secondo intero rappresenta il numero M di sponsor.

Le successive N righe rappresentano gli ingaggi degli atleti.
La i-esima di tale righe (1 ≤ i ≤ N) contiene 1+Q interi separati da uno spazio che rappresentano gli sponsor che hanno ingaggiato l’atleta i:

  • il primo intero rappresenta il numero Q di tali sponsor (0 ≤ Q ≤ M) ed è pari a 0 se l’atleta non ha sponsor;
  • i successivi Q interi (in ordine crescente) indicano quali sono i suoi sponsor se Q è positivo.

 

Dati in Output

Il file output.txt è composto da una riga contenente uno solo dei due seguenti possibili risultati:

  • l’intero 1 se tutti gli atleti e gli sponsor soddisfano il noto principio di marketing;
  • tre interi 0, A e B separati da uno spazio, se esistono degli sponsor A e B che non rispettano tale principio con i loro atleti ingaggiati.

 

Assunzioni

  • 1 ≤ N ≤ 10000
  • 1 ≤ M ≤ 10000
  • 1 ≤ A, B ≤ M e A ≠ B

 

Esempi

input.txt output.txt
1 4 3
1 2
2 1 3
0
1 1
1
2 4 3
1 2
2 1 2
1 2
2 1 3
0 1 2
Notice: This work is licensed under a BY-NC-SA. Permalink: Sponsor e atleti

Comments are closed.