In an interstellar civilisation, symbolised by a connected, undirected graph of n celestial bodies and m cosmic pathways. Each celestial body represents an alien entity, and each cosmic pathway (i, j) signifies an alliance between alien entities i and j.
In this cosmic civilisation, entity i harnesses an energy level e_i. Alien entity j feels eclipsed by entity i if e_j equals e_i + 1, implying entity j possesses exactly one more unit of energy than entity i.
The civilisation is termed as having a stellar gradient if in every allied pair, one entity feels eclipsed by the other. For some alliances, it's known which entity feels eclipsed by its ally. However, the direction of the eclipse remains unknown for the rest.
The energy disparity in this civilisation is defined as min e_i - max e_j
1 ≤ i ≤ n 1 ≤ j ≤ n
It's impossible for this civilisation to exhibit this stellar gradient with the known data, such a situation should be reported. Otherwise, a distribution of energy that fulfils the conditions for a stellar gradient should be determined and within this structure, energy disparity should be maximised.
Answer the maximum stellar gradient possible for the planet system. If no such configuration possible return -1.
Example 1:
Input: n = 6, edges = [[5, 6, 1], [3, 4, 0], [1, 4, 0], [4, 6, 0], [5, 1, 0], [4, 2, 1]]
Output: 3
Explanation:The maximum stellar gradient possible for the planet system is 3.
Example 2:
Input: n = 5, edges = [[4, 3, 1], [3, 5, 1], [2, 4, 0], [1, 2, 1], [5, 1, 1]]
Output: -1
Explanation:No such configuration is possible, hence the output is -1.
- The number of planets,
1 ≤ n ≤ 200 - The number of cosmic pathways,
1 ≤ m ≤ 2000
input:
output: