1071. Graph Coloring — M-Coloring Problem

Given an undirected graph with n nodes and edges, and an integer m, determine whether the nodes can be colored using at most m colors so that no two adjacent nodes share a color. Return true or false. The input is JSON {n, edges, m}.

Input: JSON {n, edges, m}.

Output: Boolean — true or false.

Examples

Input: {"n":4,"edges":[[0,1],[1,2],[2,3],[3,0],[0,2]],"m":3}
Output: true
Explanation: Three colors suffice.

Input: {"n":3,"edges":[[0,1],[1,2],[2,0]],"m":2}
Output: false
Explanation: A triangle needs 3 colors.

Input: {"n":1,"edges":[],"m":1}
Output: true
Explanation: One node, one color.

Constraints

• 1<=n<=20
• 1<=m<=n

Asked by