BFS

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static class Graph { List<Integer>[] graph; public Graph(int size) { graph = new List[size + 1]; } public void addEdge(int first, int second) { if (graph[first] == null){ graph[first] = new ArrayList<>(); } graph[first].add(second); if (graph[second] == null){ graph[second] = new ArrayList<>(); } graph[second].add(first); } public int[] shortestReach(int startId) { int [] distance = new int[graph.length]; for(int i = 1; i < graph.length; i++){ if(i != startId){ distance[i] = hasPathBFS(startId, i); } } return distance; } // Helper recursive BFS method private int hasPathBFS(int source, int destination){ if(graph[destination] == null){ return -1; } LinkedList<Integer> nextToVisit = new LinkedList<>(); //all nodes visited HashSet<Integer> visited = new HashSet<>(); //deph level int level = 0; List<Integer> nodesInLevel = new ArrayList<>(); nodesInLevel.add(source); Map<Integer, List<Integer>> levels = new HashMap<>(); levels.put(level, nodesInLevel); nextToVisit.add(source); List<Integer> levelsFound = new ArrayList<>(); while (!nextToVisit.isEmpty()){ int nextNode = nextToVisit.remove(); if(levels.get(level) != null && !levels.get(level).contains(nextNode)){ level--; } if (nextNode == destination){ //found at that level levelsFound.add(level); } if (visited.contains(nextNode)){ continue; } visited.add(nextNode); if(graph[nextNode] != null){ //These are in same level nodesInLevel = new ArrayList<>(); for (int child : graph[nextNode]) { nextToVisit.add(child); nodesInLevel.add(child); } //increase level level++; levels.put(level, nodesInLevel); } } int minLevel = graph.length; for(Integer levelFound: levelsFound) { if(levelFound > 0 && levelFound < minLevel){ minLevel = levelFound; } } return minLevel == graph.length ? -1 : minLevel* 6; } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int queries = scanner.nextInt(); for (int t = 0; t < queries; t++) { // Create a graph of size n where each edge weight is 6: Graph graph = new Graph(scanner.nextInt()); int m = scanner.nextInt(); // read and set edges for (int i = 0; i < m; i++) { int u = scanner.nextInt(); int v = scanner.nextInt(); // add each edge to the graph graph.addEdge(u, v); } // Find shortest reach from node s int startId = scanner.nextInt(); int[] distances = graph.shortestReach(startId); for (int i = 1; i < distances.length; i++) { if (i != startId) { System.out.print(distances[i]); System.out.print(" "); } } System.out.println(); } scanner.close(); } }