OPM 2013 Problem 3

In the Republic of Unistan there are $n$ national roads, each of them links two cities exactly. You can travel from one city to another of your choice using a sequence of roads. The President of Unistan ordered to label the national roads with the integers from $1$ to $n$ by an old law: if a city is adjacent to more than one road, the greatest common divisor of the numbers of that roads must be one. Show that you can label the national roads without breaking the law.