Optimal Graph Layering

HARD40 pts

You are tasked with organizing nodes in an undirected graph into hierarchical layers. Given a positive integer n representing the number of nodes (labeled from 1 to n), and a 2D integer array edges where each edges[i] = [uᵢ, vᵢ] indicates an undirected edge between nodes uᵢ and vᵢ, your goal is to assign each node to exactly one layer such that the following conditions are satisfied:

Complete Assignment: Every node in the graph must be assigned to exactly one layer.
Adjacent Layer Constraint: For every edge [uᵢ, vᵢ] in the graph, if node uᵢ is assigned to layer x and node vᵢ is assigned to layer y, then the absolute difference between their layer indices must be exactly 1 (i.e., |x - y| = 1).

The layers are indexed starting from 1. Note that the graph may consist of multiple disconnected components.

Return the maximum number of layers into which the nodes can be organized while satisfying all conditions. If no valid layering arrangement exists that satisfies the constraints, return -1.

Key Observations:

The adjacent layer constraint essentially requires that the graph be bipartite for any valid layering to exist. If a connected component contains an odd-length cycle, it cannot be properly layered.
For each connected component, the maximum number of layers is determined by the longest shortest path (diameter) within that component, which can be computed using BFS from each node.
The total maximum layers across the entire graph is the sum of the maximum layers achievable in each connected component.

Example

Input

n = 6
edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]

Output

4

Explanation

One optimal layering is:

Layer 1: Node 5
Layer 2: Node 1
Layer 3: Nodes 2 and 4
Layer 4: Nodes 3 and 6

Every edge connects nodes in adjacent layers (layer difference of exactly 1). For example, edge [1,2] connects layer 2 and layer 3, edge [2,6] connects layer 3 and layer 4. This arrangement uses 4 layers, which is the maximum possible.

Example

Input

n = 3
edges = [[1,2],[2,3],[3,1]]

Output

-1

Explanation

The graph forms a triangle (3-cycle). If we place node 1 in layer x, node 2 must be in layer x+1, and node 3 must be in layer x+2. However, the edge [3,1] requires |x - (x+2)| = 1, which is impossible since |2| ≠ 1. This odd-length cycle makes any valid layering impossible.

Example

Input

n = 4
edges = [[1,2],[2,3],[3,4]]

Output

4

Explanation

The graph forms a simple path: 1—2—3—4. The optimal layering assigns each node to a distinct layer in sequence:

Layer 1: Node 1
Layer 2: Node 2
Layer 3: Node 3
Layer 4: Node 4

Each edge connects consecutive layers, maximizing the total to 4 layers.

Accepted0/0·0% Acceptance

Constraints

1 ≤ n ≤ 500
1 ≤ edges.length ≤ 10⁴
edges[i].length == 2
1 ≤ uᵢ, vᵢ ≤ n
uᵢ ≠ vᵢ (no self-loops)
There is at most one edge between any pair of nodes (no multi-edges)

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

n =

edges =

[[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]

Optimal Graph Layering

Key Observations:

Hints

Optimal Graph Layering

Key Observations:

Hints