Constructing a DAG with Exactly k Paths

This problem is adapted from PA 2020 Runda 5 "Skierowany graf acykliczny".

Given a positive integer k, your task is to construct a Directed Acyclic Graph (DAG) with n nodes (numbered from 1 to n) such that there are exactly k different directed paths from node 1 to node n. Two paths are considered different if there exists at least one edge that is used in one path but not in the other.

Your graph must satisfy the following constraints:

• The total number of nodes must be at most 100.
• Each node can have at most two outgoing edges. (If a node has two outgoing edges, they must point to distinct nodes.)
• No multi-edges (i.e. duplicate edges) are allowed.

It can be proven that for every valid input k (subject to the above constraints), there exists a graph meeting these requirements.

A hint to constructing such a graph is to simulate a binary tree structure. A full binary tree naturally provides exponential growth in the number of root-to-leaf paths, and then you can choose exactly k of these paths by adding an extra terminal node and connecting a carefully selected subset of the leaves.

Formally, if we let h be the height (i.e. h = ceil(log₂(k))), then one can build a full binary tree of height h (with nodes numbered in standard heap order) and then add a new terminal node numbered 2^h+1. For each leaf (nodes numbered from 2^h to 2^h+1 - 1), if it is among the first k leaves (in left-to-right order), add an edge from that leaf to the terminal node. This construction guarantees exactly k distinct paths from node 1 (the root) to node 2^h+1 (the terminal node).

Note: In the special case when k = 1, a trivial graph with two nodes and a single edge from node 1 to node 2 is acceptable.

inputFormat

The input consists of a single integer k — the required number of distinct paths from node 1 to node n.

Constraints: It is guaranteed that there exists a solution with at most 100 nodes and at most 2 outgoing edges per node.

outputFormat

First, output two integers n and m — the total number of nodes and the total number of directed edges in your constructed graph, respectively.

Then, output m lines. Each line should contain two integers u and v representing a directed edge from node u to node v.

Your graph must satisfy the following:

• It is a DAG (directed acyclic graph) with nodes numbered from 1 to n.
• The number of distinct paths from node 1 to node n is exactly k.
• The total number of nodes is at most 100 and each node has at most 2 outgoing edges.

You may assume that for every valid input k a solution exists.

sample

1

2 1
1 2

</p>