Path count II

Construct a directed acyclic graph with the nodes $1,2,\dots,100$. The graph should have exactly $x$ different paths from the node $1$ to the node $100$. The graph can have at most $1000$ edges, and each edge must be unique.

In a file paths2.py, implement the function create_edges the returns the graph as a list of the edges. For example, the list [(1, 2), (4, 5)] represents a graph with the two edges $1 \rightarrow 2$ and $4 \rightarrow 5$.

You can assume that $x$ is in the range $0 \dots 10^9$ in all tests.

You can test your function using the class CountPaths in the course material. In the code template below, the method count_paths should return $123456789$, when the graph is correctly constructed.

class CountPaths:
    # you can copy this class from the course material

def create_edges(x):
    # TODO

if __name__ == "__main__":
    edges = create_edges(123456789)

    counter = CountPaths(range(1, 100 + 1))
    for edge in edges:
        counter.add_edge(edge[0], edge[1])
    print(counter.count_paths(1, 100)) # 123456789