import java.util.*;

public class Graf {
    private Map<Integer, List<Integer>> adjList;

    // Konstruktor za graf
    public Graf() {
        adjList = new HashMap<>();
    }

    // Dodavanje vrha grafu
    public void addVertex(int vertex) {
        adjList.putIfAbsent(vertex, new ArrayList<>());
    }

    // Dodavanje usmerene ivice
    public void addEdge(int source, int destination) {
        adjList.putIfAbsent(source, new ArrayList<>());
        adjList.putIfAbsent(destination, new ArrayList<>());
        adjList.get(source).add(destination);
    }

    // Prikazivanje grafa
    public void printGraph() {
        System.out.println("Graf:");
        for (int vertex : adjList.keySet()) {
            System.out.print(vertex + " -> ");
            System.out.println(adjList.get(vertex));
        }
    }

    // Breadth-First Search (BFS)
    public void bfs(int start) {
        System.out.println("\nBFS počevši od vrha " + start + ":");
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> red = new LinkedList<>();

        visited.add(start);
        red.offer(start);

        while (!red.isEmpty()) {
            int current = red.poll();
            System.out.print(current + " ");

            for (int neighbor : adjList.get(current)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    red.offer(neighbor);
                }
            }
        }
        System.out.println();
    }

    // Depth-First Search (DFS)
    public void dfs(int start) {
        System.out.println("\nDFS počevši od vrha " + start + ":");
        Set<Integer> visited = new HashSet<>();
        dfsHelper(start, visited);
        System.out.println();
    }

    // Helper metod za DFS
    private void dfsHelper(int vertex, Set<Integer> visited) {
        visited.add(vertex);
        System.out.print(vertex + " ");

        for (int neighbor : adjList.getOrDefault(vertex, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfsHelper(neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        Graf graf = new Graf();

        // Dodavanje ivica grafu
        graf.addEdge(0, 1);
        graf.addEdge(0, 2);
        graf.addEdge(1, 2);
        graf.addEdge(2, 0);
        graf.addEdge(2, 3);
        graf.addEdge(3, 3);

        // Prikazivanje grafa
        graf.printGraph();

        // BFS i DFS obilasci
        graf.bfs(2);
        graf.dfs(2);

    }
}