atena

Atena

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~}$.

Din păcate Parmenide a murit în timp ce încerca să ajungă la Congresul de Matematică Aplicată din Siracuza, aşa că sarcina lui v-a revenit vouă. Totuşi Parmenide a menţionat în treacăt înainte să plece că rezolvarea problemei se bazează în mod esenţial pe următoarele două proprietăţi ale reţelei stradale din Atena:
 
* $N{~1~} ≥ 2 * M{~2~}$;
* b
 

h2. Date de intrare
Fişierul de intrare $atena.in$ ...