Perché la mucca ha attraversato la strada III (Argento)#10537
La fattoria di John è una griglia quadrata di dimensioni n \times n, composta da campi. Alcune coppie di campi adiacenti (situati a nord-sud o a ovest-est) sono separate da strade, e lungo l'intero perimetro esterno della griglia corre un'alta recinzione che non permette alle mucche di lasciare la fattoria. Le mucche possono muoversi liberamente tra campi adiacenti nelle direzioni nord, est, sud e ovest, tuttavia preferiscono non attraversare le strade se non strettamente necessario.
Nella fattoria di Farmer John si trovano mucche, ciascuna situata in un campo separato. Una coppia di mucche è detta «distante» se, affinché una mucca possa raggiungere l'altra, è necessario attraversare almeno una strada. Aiuta Farmer John a contare il numero di coppie di mucche «distanti».
La prima riga contiene tre numeri interi e r~(2 \le n \le 100, 1 \le k \le 100, k \le n^2). Nelle successive righe sono descritte le strade che separano le coppie di campi adiacenti. Ogni riga è nella forma r~c~r'~c' (numeri interi nell'intervallo ), indicando la presenza di una strada tra il campo nella riga , colonna , e il campo adiacente nella riga r', colonna c'. Nelle ultime righe è indicata la posizione delle mucche — per ogni mucca sono forniti il numero di riga e il numero di colonna del suo campo.
Stampa il numero di coppie di mucche che sono «distanti».
Esempio 1