CodeForces 1009 D.Relatively Prime Graph(构造,gcd)
题意:要求构造n个点m条边的连通图满足,相连的点的gcd为1(互质)如果可以,输出Possible和m条边的端点如果不行,输出Impossible思路:首先要保证图连通,至少需要n-1条边,则如果m小于n-1,一定不可能因为相邻的两个数互质,则可以先建立一条链(1->2,2->3,3->4),一共n-1条边,这样就满足连通了。然后不足m的边随便加加就行了,直接暴力...