class Solution
{
	public:
	//Function to find the level of node X.
	using pi = pair<int,int>;
	int nodeLevel(int V, vector<int> adj[], int X) 
	{
	    // code here
	    vector<bool> vis(V, false);
	    queue<pi> q;
	    q.push({0, 0});
	    vis[0] = true;
	    while(!q.empty()){
	        auto curr = q.front();q.pop();
	        if(curr.first == X)
	            return curr.second;
	       for(auto adjV : adj[curr.first]){
	           if(!vis[adjV]){
	               vis[adjV] = true;
	               q.push({adjV , curr.second + 1});
	           }
	       }
	    }
	    return -1;
	}
};

class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        vector<vector<int>> gr(n+1);
        vector<int> indegree(n+1, 0), prev_time(n+1, 0);
        for(auto& edge : relations){
            gr[edge[0]].push_back(edge[1]);
            indegree[edge[1]]++;
        }
        time.insert(time.begin(), 0);
        queue<int> q;
        for(int i =1; i <= n; i++)
            if(indegree[i] == 0)
                q.push(i);
        while(!q.empty()){
            int node = q.front();q.pop();
            for(auto adjV : gr[node]){
                prev_time[adjV] = max(prev_time[adjV] , time[node] + prev_time[node]);
                if(--indegree[adjV] == 0)
                    q.push(adjV);
            }
        }
        int ans = 0;
        for(int i =1 ; i < n + 1; ++i){
            ans = max(ans, time[i]+prev_time[i]);
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        vector<int> indegree(n, 0), ans;

        for(auto e : edges){
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
            indegree[e[0]]++;
            indegree[e[1]]++;
        }
        queue<int> q;
        for(int i = 0; i < n ;i++)
            if(indegree[i] == 1)
                q.push(i), indegree[i]--;
        
        while(!q.empty()){
            int s = q.size();
            ans.clear();
            for(int i = 0 ; i < s ;i++){
                int curr = q.front(); q.pop();
                ans.push_back(curr);
                for(auto child : graph[curr])
                {
                    indegree[child]--;
                    if(indegree[child] == 1)
                        q.push(child);
                }
            }
        }
        if(n == 1)ans.push_back(0);
        return ans;
    }
};

class Solution {
    using Index = pair<int, int>;
    vector<Index> directions =
    {
        {-1, -1},
        {-1, 0},
        {-1, 1},
        {0, -1},
        {0, 1},
        {1, -1},
        {1, 0},
        {1, 1}
    };

public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid)
    {
        const int n = grid.size();
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1)
            return -1;

        if (n == 1)
            return 1;
        
        int distance = 1;
        Index target = {n - 1, n - 1};
        queue<Index> q;
        q.push({0, 0});
        grid[0][0] = 1;
        while (!q.empty())
        {
            const int levelSize = q.size();
            for (int i = 0; i < levelSize; i++)
            {
                Index curr = q.front();
                q.pop();
                for (const Index& diff : directions)
                {
                    Index next = {curr.first + diff.first, curr.second + diff.second};
                    if (next.first >= 0 && next.first < n && next.second >= 0 && next.second < n 
                        && grid[next.first][next.second] == 0)
                    {
                        if (next == target)
                            return distance + 1;
                        grid[next.first][next.second] = 1;
                        q.push(next);
                    }
                }
            }
            distance++;
        }
        return -1;
    }
};

#include<stdio.h>

void BFS(int);
int graph[10][10], visited[10],total;

main()
{
	int i,j;
	printf("\nEnter the total number of vertices in graph\n");
	scanf("%d",&total);
	/*Adjacency matrix input*/
	printf("\nEnter the adjacency matrix\n");
	for(i=0;i<total;i++)
	{
		for(j=0;j<total;j++)
		{
			scanf("%d",&graph[i][j]);
		}
	}
	for(i=0;i<total;i++)
	{
		visited[i] = 0;
	}
	printf("\nBFS traversal is \n");
	BFS(0);
}
void BFS(int vertex)
{
	int j;
	printf("%d\t",vertex);
	visited[vertex] = 1;
	for(j=0;j<total;j++)
	{
		if(!visited[j] && graph[vertex][j] == 1 )
		{
			BFS(j);
		}
	}
}

class Solution {
    public:
    int closedIslands(vector<vector<int>>& matrix, int N, int M) {
        // Code here
        queue<pair<int,int>> q;
        for(int i = 0; i < N ; i++){
            for(int j = 0; j < M; j++){
                if(matrix[i][j] == 1 && (i == 0 || j == 0 || i == N-1 || j == M-1))
                    q.push({i,j}),matrix[i][j] = 0;
            }
        }
        auto bfs = [&q,&matrix,N,M]()->void{
            auto isSafe = [N, M](int x, int y)->bool{
                return x>=0 && y>=0 && x<N && y<M;
            };
            while(!q.empty()){
            auto curr = q.front();
            q.pop();
            vector<pair<int,int>> dir{
                {1,0},
                {0,-1},
                {-1,0},
                {0,1}
            };
            for(auto p : dir){
                int x = p.first+ curr.first , y = p.second + curr.second;
                if(isSafe(x, y) && matrix[x][y] == 1 )
                    q.push({x,y}), matrix[x][y] = 0;
            }
            }
        };
        bfs();
        int ans = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0 ; j<M; j++){
                if(matrix[i][j]){
                    matrix[i][j] = 0;
                    q.push({i,j});
                    bfs(),ans++;
                }
            }
        }
        return ans;
    }
};