Paths

Your task is to construct a directed acyclic graph with 100 nodes and exactly x different paths from the node 1 to the node 100. The graph can have at most 1000 edges and every edge must be different.

For example, when x=5, one possible solution consists of the edges (1,3),(1,5),(2,100),(3,2),(3,100),(5,2),(5,3). In this case, the paths are:

• 1 \rightarrow 3 \rightarrow 100
• 1 \rightarrow 3 \rightarrow 2 \rightarrow 100
• 1 \rightarrow 5 \rightarrow 2 \rightarrow 100
• 1 \rightarrow 5 \rightarrow 3 \rightarrow 100
• 1 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 100

You may assume that x is an integer in the range 1 \dots 10^9. You can construct any graph that satisfies the conditions.

In a file paths.py, implement a function create that returns the graph as a list of edges.

def create(x):
    #TODO

if __name__ == "__main__":
    print(create(2)) # esim. [(1,2), (1,100), (2,100)]
    print(create(5))
    print(create(10))
    print(create(123456789))