Directed Graph with Specified Arborescence Count

You are given two integers n and k. Consider vertices numbered from 1 to n, with 1 designated as the root. A directed spanning tree (also called an out‐branching) is a subgraph in which every vertex except 1 has exactly one incoming edge and all vertices are reachable from 1. A directed graph may contain self-loops and multiple (parallel) edges.

Your task is to construct a directed graph with at most 100 edges such that the number of spanning arborescences (i.e. directed spanning trees rooted at 1) is exactly k, or determine that it is impossible.

The graph you construct should have its vertices numbered from 1 to n. The output graph is represented by an integer m (the number of edges) followed by m lines, each line containing two integers u and v representing a directed edge from u to v.

Notes:

• If n = 1, by convention the only spanning tree is the trivial one. Thus, a valid graph exists only when k = 1.
• If n > 1 and k = 0, you may output a graph in which not all vertices are reachable from vertex 1 (for example, an edgeless graph) so the number of spanning trees is 0.
• If n > 1 and k > 0, note that a spanning tree on n vertices has exactly n-1 edges. If you form a spanning tree and choose one edge (say, from 1 to 2) to have d parallel copies while all other edges appear only once, the total number of spanning trees equals d (since that edge can be chosen in d ways). In our construction, we use a simple chain: add k copies of edge (1,2) and then for each i from 2 to n-1 add an edge from i to i+1. This yields exactly k spanning trees. However, note that the total number of edges becomes k + (n - 2) which must be ≤ 100. Hence a necessary condition for n > 1 and k > 0 is k + n - 2 ≤ 100 (or equivalently k ≤ 102 - n).

If a construction is impossible, simply output -1.

inputFormat

The input consists of a single line containing two space‐separated integers n and k:

• n (number of vertices, 1 ≤ n ≤ 101)
• k (the desired number of spanning arborescences)

outputFormat

If a valid graph construction exists, first output an integer m representing the number of edges, followed by m lines each containing two space‐separated integers u and v denoting a directed edge from u to v. The graph must have at most 100 edges.

If no valid construction exists, output a single line containing -1.

sample

1 1

0