홀의 정리

정점이 왼쪽 부분과 오른쪽 부분으로 나뉘어 있는 이분 그래프를 생각해 보자. 간선은 서로 다른 부분에 속한 정점 사이에만 있다. $A$를 왼쪽 부분 정점들의 부분집합이라 하자. $N(A)$는 $A$의 정점 중 하나 이상과 인접한 오른쪽 부분 정점들의 집합이다.

왼쪽 부분 정점들의 부분집합 $A$가 $|N(A)| < |A|$를 만족하면 $A$를 임계 부분집합이라 한다.

왼쪽 부분에 정점이 $n$개, 오른쪽 부분에 정점이 $n$개이고, 임계 부분집합이 정확히 $k$개인 이분 그래프를 찾으시오.

첫 줄에 두 정수 $n$과 $k$가 주어진다. $n$은 그래프의 각 부분에 있는 정점의 수이고, $k$는 필요한 임계 부분집합의 개수이다 ($1 \le n \le 20$, $0 \le k < 2n$).

첫 줄에 간선의 수 $m$을 출력한다. 이어서 $m$개의 줄에 각각 간선을 나타내는 두 정수 $a_i$, $b_i$ ($1 \le a_i, b_i \le n$)를 출력한다. 이는 $a_i$에서 $b_i$로 가는 간선이다.

그래프에 중복 간선이 있으면 안 되며, 임계 부분집합이 정확히 $k$개여야 한다. 조건을 만족하는 그래프가 여러 개이면 그중 아무거나 출력한다. 주어진 제약 조건에서 답은 항상 존재한다.