Given a graph with <= 1,000 nodes and <= 5,000 edges. Additionally, you are given a subset U of at most 10 nodes. It is guaranteed every node not in U is adjacent to at least one node in U.

Find a 3-colouring of the graph or determine no 3-colouring is possible.

Possible back story:
N employees are going on a retreat. A small subset of them are executives. Some pairs of employees work closely together. Every non-executive works closely with at least one executive (a suggestion from the previous retreat).

There are three activities available on the day of the retreat. You want to divide the employees between these three activities but are worried that if two employees that work closely together are part of the same group then they might be less inclined to work with others in the same group. So determine if it is possible to assign employees to groups so that no group has a pair that works closely together.