Polut

Tehtäväsi on muodostaa syklitön suunnattu verkko, jossa on $100$ solmua ja tasan $x$ erilaista polkua solmusta $1$ solmuun $100$. Verkossa saa olla korkeintaan $1000$ kaarta ja jokaisen kaaren tulee olla erilainen.

Esimerkiksi kun $x=5$, yksi mahdollinen ratkaisu muodostuu kaarista $$(1,3),(1,5),(2,100),(3,2),(3,100),(5,2),(5,3).$$ Tässä tapauksessa polut ovat seuraavat:

• $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$

Voit olettaa, että $x$ on kokonaisluku välillä $1 \dots 10^9$. Voit muodostaa minkä tahansa verkon, joka täyttää yllä olevat vaatimukset.

Toteuta tiedostoon paths.py funktio create, joka palauttaa verkon rakenteen listana kaaria tupleina.

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))