No. (left, ship for left) and (right, ship for right) are two segments which enclose current part of plane. Ships that are inside this part can be found in O(n) time (check for each ship in O(1)). Please read my code if you don't understand yet.

int fa[1000005];
int getfa(int x)
{
	return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
class GCDGraph
{
public:
	string possible(int n, int k, int x, int y)
	{
		for (int i = 1; i <= n; i++)
		{
			fa[i] = i;
		}
		for (int i = 1; i <= n; i++)
		{
			if (i <= k)continue;
			int h = getfa(i);
			for (int j = i; j <= n; j += i)
			{
				int g = getfa(j);
				fa[g] = h;
			}
		}
		if (getfa(x) == getfa(y))
		{
			return "Possible";
		}
		else
		{
			return "Impossible";
		}
	}
};

What I did was find all the vertices which can be visited from x, and find all the vertices which can be visited from y. Then if we can find a path from any vertex which can be visited from x(say a) to any vertex which can be visited from y(say b) we have a path from x to y. (The path is x-a-b-y).

Ok, naturally this doesn't work on regular graphs which don't have automorphisms. On the Frucht graph your program outputs 12 while the answer is 1. It has 12 vertices and 18 edges though so this doesn't quite fit, but you get the kind of problems this solution can meet.

An example suitable for the constraints (from this page) with 8 vertices and 12 edges: (0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 1), (3, 6), (6, 5), (5, 4), (7, 0), (7, 5), (7, 6). The answer is 4, but your solution should naturally output something divisible by 8 (in fact, it outputs 16).

The same problem appeared in the last day contest on 2016 winter Petrozavodsk camp. The contest is curiously dubbed "Grand Prix of China" but I don't know the exact origin of the problem (probably snarknews can shed some light here).

The idea is roughly as follows: first we can successively erase all leaves (degree-1 vertices), they will form several trees. Then we contract paths of degree-2 vertices. The resulting "minimized" graph will have vertices of degree 3 or more, hence it will contain at most 10 vertices (note that we never changed the |E| - |V| parameter). Now the answer is the product of:

• the number of automorphisms for each tree
• the number of ways to interchange isomorphic paths connecting the same pair of "minimized" graph vertices
• the number of automorphisms of the "minimized" graph that preserve the multiset of paths between each pair of vertices

Equivalences can be checked with lots of hashing on trees, paths, sets of paths, etc. The last part (automorphisms of minimized graph) can be computed explicitly by trying all permutations.