Fewest Colours for a Seating Chart

A wedding planner has n guests numbered 0..n-1 and a list feuds of pairs [a, b] of guests who must not sit at the same table. Tables are unlimited in size. Return the smallest number of tables needed so that no feuding pair shares a table. With no guests, return 0.

Examples

Input:  n = 4, feuds = [[0, 1], [1, 2], [2, 0], [2, 3]]
Output: 3
Explanation: 0, 1 and 2 all feud with each other, so three tables are needed;
            guest 3 can join guest 0's table.

Input:  n = 4, feuds = []
Output: 1

Input:  n = 5, feuds = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0]]
Output: 3
Explanation: a ring of five cannot alternate between two tables.

Constraints

• 0 <= n <= 11, pairs are distinct and a != b

Goals

• Decide whether a graph can be coloured with k colours by backtracking
• Find the minimum by trying increasing k