Pericle, regele Atenei, a decis să afle în ce măsură reţeaua de străzi a Spartei este asemănătoare cu reţeaua de străzi a oraşului Atena. În acest scop, el i-a cerut unuia dintre matematicienii atenieni, Parmenide, să afle dacă reţeaua de străzi a Spartei este inclusă în reţeaua de străzi a Atenei.

Pericle consideră că reţeaua de străzi a Spartei este inclusă în reţeaua de străzi a Atenei dacă şi numai dacă există submulţimi disjuncte două câte două nevide $A{~1~}, A{~2~}, ..., A{~N{~i~}~}$ ale mulţimii ${ 1, 2, ..., N{~i~} }$ cu proprietatea că pentru orice drum între două intersecţii $N{~1~} + a$ şi $N{~1~} + b$ în Sparta există un drum între o intersecţie $c$ şi o intersecţie $d$ în Atena, cu $c din A{~a~}$, $d din A{~b~}$ şi $1 <= a, b <= N{~2~}$, $1 <= c, d <= N{~1~}$.

h2. Date de intrare