class Node{
    public:
    Node* list[26];

    Node(){
        for(int i=0; i<26; i++){
            list[i] = NULL;
        }
    }

    bool containsKey(char c){
        return list[c - 'a'] != NULL;
    }

    Node* get(char c){
        return list[c - 'a'];
    }

    void put(char c, Node* node){
        list[c - 'a'] = node;
    }
};

int countDistinctSubstrings(string &s)
{
    int cnt = 0;
    Node* root = new Node;
    
    for(int i=0; i<s.size(); i++){
        Node* node = root;
        for(int j=i; j<s.size(); j++){
            if(!node->containsKey(s[j])){
                cnt++;
                node->put(s[j],new Node);
            }
            node = node->get(s[j]);
        }
    }

    return cnt + 1;
}

#include <bits/stdc++.h>
using namespace std;

void topoSort(int node, unordered_map<int,bool> &isVisited, stack<int> &s, unordered_map<int,list<pair<int,int>>> &adj){
    
    isVisited[node] = true;

    for(auto neighbours : adj[node]){
        if(!isVisited[neighbours.first]){
            topoSort(neighbours.first, isVisited, s, adj);
        }
    }

    s.push(node);
    return;
}

vector<int> shortestPathInDAG(int n, int m, vector<vector<int>> &edges)
{

    // Step 1 -> Create Topological Order Stack
    
        //Step (a) -> Mapping of adj
            
            unordered_map<int,list<pair<int,int>>> adj;
            
            for(int i=0; i<m; i++){
                int x = edges[i][0];
                int y = edges[i][1];
                int dist = edges[i][2];

                adj[x].push_back({y,dist});
            }
            
        //Step (b) -> Creating isVisited
        
            unordered_map<int,bool> isVisited;
            
        //Step (c) -> Creating Stack
        
            stack<int> s;
        
        //Step (d) -> Calling DFS method function to fill the stack

            for(int i=0; i<n; i++){
                if(!isVisited[i]){
                    topoSort(i, isVisited, s, adj);
                }
            }
    
    // Step 2 -> Creating result answer vector

        // Declaring the src node
        int src = 0;
        
        // Declaring the dist vector
        vector<int> dis(n,INT_MAX);

        // Setting the values in dis vector
        dis[src] = 0;
        while(!s.empty()){
            int top = s.top();
            s.pop();

            if(dis[top]!=INT_MAX){
                for(auto i:adj[top]){
                    if(dis[top] + i.second < dis[i.first]){
                        dis[i.first] = dis[top] + i.second;
                    }
                }
            }
        }

        for(int i=0; i<n; i++){
            if(dis[i]==INT_MAX){
                dis[i] = -1;
            }
        }

        return dis;
}

vector<int> bfsTraversal(int n, vector<vector<int>> &adj){
    // Write your code here.

    vector<int> res;

    // adj is adjacency list
    // n is number of nodes

    // Steps

    // Step 1 -> create a map for knowing if a node is visited or not
    unordered_map<int,bool> isVisited;

    for(int i=0; i<n; i++){
        isVisited[i] = false;
    }

    // Step 2 -> create a queue

    queue<int> q;
    q.push(0);

    // Step 3 -> while poping out of the queue we run the while loop
    while(!q.empty()){
        int frontNode = q.front();
        q.pop();

        if(!isVisited[frontNode]){
            isVisited[frontNode] = true;
            res.push_back(frontNode);
            for(auto i:adj[frontNode]){
                q.push(i);
            }
        }
    }

    return res;

}