소는 왜 길을 건너갔을까? 6 timer 2s memory 512MB

소는 왜 길을 건너갔을까? 그 이유 중 하나는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 돌아다닐 수가 없다. 그래서 존의 농장에 대대적인 리모델링이 있었다.

이제 존의 농장은 N^2개의 작은 정사각형 목초지가 N \times N 격자 정사각형 형태로 이루어져 있다. 기본적으로 소들은 인접한 목초지 사이를 자유롭게 동서남북으로 이동할 수 있지만, 그 중 일부는 목초지 사이에 길이 놓여있어 길을 건너야 한다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다.

존의 농장의 K마리의 소가 있고, 각 소는 서로 다른 목초지에 있다. 어떤 두 소는 길을 건너지 않고는 절대 만나지 못 할 수 있는데, 이런 소가 몇 쌍인지 세어보자.