406115: GYM102268 H Hall's Theorem

Consider a bipartite graph with vertices grouped into two parts, left and right, and edges only between vertices from different parts. Let $$$A$$$ be a subset of vertices from the left part. We define $$$N(A)$$$ as the set of vertices from the right part which are adjacent to at least one vertex in $$$A$$$.

A subset $$$A$$$ of vertices from the left part is critical if $$$|N(A)| < |A|$$$.

Your task is to find a bipartite graph which has $$$n$$$ vertices in the left part, $$$n$$$ vertices in right part, and exactly $$$k$$$ critical subsets.

The first line contains two integers $$$n$$$ and $$$k$$$: the number of vertices in each part of the bipartite graph and the required number of critical subsets ($$$1 \leq n \leq 20$$$, $$$0 \leq k < 2^n$$$).

On the first line, print one integer $$$m$$$: the number of edges in your bipartite graph.

The next $$$m$$$ lines must describe the edges of your graph. Each of them must contain two integers $$$a_i$$$ and $$$b_i$$$, describing the edge from $$$a_i$$$ to $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$).

The graph must contain no multiple edges. Additionally, it must have exactly $$$k$$$ critical subsets.

If there are several possible solutions, print any one of them. It is guaranteed that the solution always exists under the given input constraints.

3 5

2
1 1
2 1