if your algo use euleraen tour and also add edge to the graph, note that the edge can be over that 20000.
this test is good:
20000 19999
1 2
1 3
1 4
.
.
.
1 20000

GOOD LUCK & HAPPY NEW YEAR!!!