Given a directed graph as an adjacency list, you will determine, in this challenge, the breath first search distance of all nodes from a starting vertex, s, assuming that the weight of each edge is 1.

In the example graph above, for s=0, the distances of each vertex from s are

0 1 1 2 3 

The output includes the distances for the vertices, 0, 1, 2, 3, 4, in the order of the vertex number.

If s=1, then the output will be

-1 0 -1 1 2 

For the starting vertex 1, the vertex 0 and 2 are unreachable, so the corresponding BFS distances are -1 and -1.

Input Format

• First line in the input contains the starting vertex s
• Each of the subsequent lines contains two space-separated integers, v and w, that represents an edge from the node v to w.

Constraints

Node numbers are 0 based, i.e. if there n nodes, the nodes are numnered as 0,1,2,...,n-1.

Output Format

Print the distace of each vertex from the start vertex in the order of the vertex number.

Sample Input 0

0 0 1 0 2 1 3 3 4 

Sample Output 0

0 1 1 2 3 

Sample Input 1

1 0 1 0 2 1 3 3 4 

Sample Output 1

-1 0 -1 1 2 

import java.io.*; import java.util.*; import java.util.stream.Collectors;

public class Solution {

public static class DirectedGraph { /* Adjacency List representation of the given graph */ private Map> adjList = new HashMap>();

public String toString() { StringBuffer s = new StringBuffer(); for (Integer v : adjList.keySet()) s.append(" " + v + " -> " + adjList.get(v)); return s.toString(); }

public void add(Integer vertex) { if (adjList.containsKey(vertex)) return; adjList.put(vertex, new ArrayList()); }

public void add(Integer source, Integer dest) { add(source); add(dest); adjList.get(source).add(dest); }

/* Indegree of each vertex as a Map */ public Map inDegree() { Map result = new HashMap(); for (Integer v : adjList.keySet()) result.put(v, 0); for (Integer from : adjList.keySet()) { for (Integer to : adjList.get(from)) { result.put(to, result.get(to) + 1); } } return result; }

public Map outDegree() { Map result = new HashMap(); for (Integer v : adjList.keySet()) result.put(v, adjList.get(v).size()); return result; }

}

// Complete the bfsDistance function below. public static Map bfsDistance(DirectedGraph digraph, Integer start) { Map distance = new HashMap(); return distance; }

public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

int sVertex = Integer.parseInt(bufferedReader.readLine().trim());

DirectedGraph digraph = new DirectedGraph();

String line; while ((line = bufferedReader.readLine()) != null) { String[] v = line.split(" "); digraph.add(Integer.parseInt(v[0]), Integer.parseInt(v[1])); } Map bfsd = bfsDistance(digraph, sVertex); String s = bfsd.entrySet().stream().map(e -> String.valueOf(e.getValue())).collect(Collectors.joining(" ")); bufferedWriter.write(s); bufferedReader.close(); bufferedWriter.close(); } }