Vertices and edges
Dag
Shortest path algorithm
Topological sorting
Graphs
Algorithms
Shortest path algorithms
89.0% success
2,661 attempts
1.5s time
256MB memory
1024KB max code

You are given an undirected weighted graph with \(n\) vertices and \(m\) edges.

Consider all shortest paths between vertices \(1\) and \(n\), for any vertex such as \(v\ (1 \le v \le n)\), say that, if \(v\) is in either all shortest paths or some of them or none of them.

Input format

  • The first line contains two integers \(n, m\) denoting the number of the graph's vertices and edges respectively.
  • Each of the following \(m\) lines contains space-separated \(v_i, u_i\), and \(w_i\) describing the graph's \(i^{th}\) edge's vertices (\(v_i, u_i\)) and its weight (\(w_i\)).

Output format

Print \(n\) lines where the \(i^{th}\) line contains either \(all\) if vertex \(i\) is in all shortest paths between \(1\) to \(n\) or \(some\) if vertex \(i\) is in some of shortest paths or \(none\) otherwise.

Constraints

\(1 \leq n \leq 2 \times 10^5\)
\(1 \leq m \leq 3 \times 10^5\)

\(1 \leq v_i, u_i \leq n\)
\(1 \leq w_i \leq 10^9\)

It is guaranteed that there are no multiple edges or self-loops in the graph.
Also, it is guaranteed that the graph is connected.

Examples
Input
6 8
2 3 7
4 1 20
5 1 5
6 5 18
3 6 10
2 4 8
5 4 7
5 2 5
Output
all
none
none
none
all
all
Explanation

The only shortest path is \(1, 5, 6\), so they are in all shortest paths and others are in no shortest paths.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...