using System;
using System.Collections.Generic;

class Graph
{
    private int _vertices;
    private List<int>[] _adjacencyList;

    public Graph(int vertices)
    {
        _vertices = vertices;
        _adjacencyList = new List<int>[vertices];
        for (int i = 0; i < vertices; i++)
        {
            _adjacencyList[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w)
    {
        _adjacencyList[v].Add(w);
    }

    public List<int> BFS(int start, int goal)
    {
        bool[] visited = new bool[_vertices];
        int[] parent = new int[_vertices];
        Queue<int> queue = new Queue<int>();
        List<int> path = new List<int>();

        for (int i = 0; i < _vertices; i++)
        {
            parent[i] = -1;
        }

        visited[start] = true;
        queue.Enqueue(start);

        while (queue.Count != 0)
        {
            int current = queue.Dequeue();

            if (current == goal)
            {
                int temp = goal;
                while (temp != -1)
                {
                    path.Add(temp);
                    temp = parent[temp];
                }
                path.Reverse();
                return path;
            }

            foreach (int neighbor in _adjacencyList[current])
            {
                if (!visited[neighbor])
                {
                    visited[neighbor] = true;
                    parent[neighbor] = current;
                    queue.Enqueue(neighbor);
                }
            }
        }

        return path; // Return empty path if goal is not reachable
    }
}

class Program
{
    static void Main()
    {
        Graph graph = new Graph(6);
        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(2, 3);
        graph.AddEdge(3, 4);
        graph.AddEdge(4, 5);

        List<int> path = graph.BFS(0, 5);

        Console.WriteLine("Path from 0 to 5:");
        foreach (int node in path)
        {
            Console.Write(node + " ");
        }
    }
}