n nodes numbered 1 to n; its links are listed in links, each one a pair [a, b]. The graph may be disconnected.
Place the nodes into layers numbered 1, 2, …, m so that:
- each node lands in exactly one layer;
- for every link [a, b], the layer numbers of a and b differ by exactly 1.
Return the largest possible number of layers m, or -1 if no such placement exists.n=5, links=[[1, 2], [2, 3], [3, 4], [2, 5]] → 4
Layers {1}, {2}, {3, 5}, {4}: every link joins neighbouring layers. A fifth layer is impossible, since the longest shortest path (from 1 to 4) has 4 nodes.
n=4, links=[[1, 2], [2, 3], [3, 1]] → -1
Nodes 1, 2, 3 form a triangle: linked nodes must sit in adjacent layers, which three mutually linked nodes cannot do. The answer is -1.
n=4, links=[[1, 2], [3, 4]] → 4
Two separate pairs, two layers each, 4 in total.
n=5, links=[[1, 2], [2, 3], [3, 4], [2, 5]]
4
Run checks the first 3 tests in your browser. Submit checks all 85 tests on the server, hidden ones included.