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

//✅ Accepted

class Edge{
public:
    int to ,cost;
};
using GRAPH2 = vector<unordered_set<int>>;
using GRAPH = vector<vector<Edge>>;

void add_edge(GRAPH &graph , int from , int to ,int cost){
    graph[from].push_back({to,cost});
    //graph[to].push_back({from,cost});
}

void print_graph(GRAPH &graph){
    for(int i = 1 ; i < graph.size() ; i++){
        cout << i << " : ";
        for(auto j : graph[i]){
            cout << j.to << " " << j.cost << " ";
        }
        cout << endl;
    }
}

//Hw 2 : Prolem 1
void solve() {
    int n,e;
    cin >> n >> e;

    unordered_map<string, vector<pair<string, int>>> g;
    set<string> nodes;

    while (e--) {
        string from, to;
        int cost;
        cin >> from >> to >> cost;
        g[from].push_back({to, cost});
        nodes.insert(from);
        nodes.insert(to);
    }

    for (const auto &node : nodes) {
        auto &edges = g[node];
        sort(edges.begin(), edges.end(), [](const auto &a, const auto &b) {
            if (a.first == b.first)
                return a.second < b.second;
            return a.first < b.first;
        });
        cout <<"\n";
        if(edges.size() == 0) continue; 
        cout <<"Flights From "<< node << " : " << '\n';
        for (const auto &edge : edges) {
            cout <<setw(10)<<"To "<< edge.first << " with cost : " << edge.second << endl;
        }
        cout << endl;
    }
}
void add_edge2(GRAPH &graph, int from, int to, int cost) {
    graph[from].push_back({to, cost});
    
}

void print_graph2(const GRAPH &graph, const vector<string> &index_to_name) {
    for (int i = 0; i < graph.size(); i++) {
        if (graph[i].empty()) continue;

        cout << "Flights from " << index_to_name[i] << ":\n";
        for (const auto &edge : graph[i]) {
            cout << setw(10) << "To " << index_to_name[edge.to] << " with cost " << edge.cost << '\n';
        }
        cout << endl;
    }
}

//Hw 2 : Prolem 2
void solve2() {
    int n, e;
    cin >> n >> e;

    map<string, int> name_to_index;
    vector<string> index_to_name;
    int idx = 0;

    GRAPH g(n); 

    while (e--) {
        string from, to;
        int cost;
        cin >> from >> to >> cost;

        if (name_to_index.find(from) == name_to_index.end()) {
            name_to_index[from] = idx++;
            index_to_name.push_back(from);
        }

        if (name_to_index.find(to) == name_to_index.end()) {
            name_to_index[to] = idx++;
            index_to_name.push_back(to);
        }

        int u = name_to_index[from];
        int v = name_to_index[to];

        add_edge2(g, u, v, cost);
    }

    print_graph2(g, index_to_name);
}
//Hw 2 : Prolem 3
void solve3() {
    int r,c;
    cin >> r >> c;
    int img[r][c] = {0};
    
    int val =0;
    for(int i = 0 ; i < r ; i++){
        for(int j = 0 ; j < c ; j++){
            img[i][j] = val++;
        }
    }
    
    vector<vector<vector<int>>> neighbors(r, vector<vector<int>>(c));
    
    for(int i = 0 ; i < r ; i++){
        for(int j = 0 ; j < c ; j++){
            if(i > 0) neighbors[i][j].push_back(img[i-1][j]);
            if(i < r-1) neighbors[i][j].push_back(img[i+1][j]);
            if(j > 0) neighbors[i][j].push_back(img[i][j-1]);
            if(j < c-1) neighbors[i][j].push_back(img[i][j+1]);
        }
    }

    for(int i = 0 ; i < r ; i++){
        for(int j = 0 ; j < c ; j++){
            cout <<"Node : "<< img[i][j] << " has neighbors : ";
            for(auto x : neighbors[i][j]){
                cout << x << " ";
            }
            cout << endl;
        }
    }
}
//Hw 2 :Prolem 4
void solve4() {
    int n, e;
    cin >> n >> e;
    list<int> g[n]; 

    while (e--) {
        int from, to;
        cin >> from >> to;
        g[from].push_back(to);
    }

    int q;
    cin >> q;
    while (q--) {
        int node;
        cin >> node;

        vector<bool> visited(n, false);
        list<int> queue; 
        queue.push_back(node);
        visited[node] = true;

        while (!queue.empty()) {
            int current = queue.front();
            queue.pop_front(); 

            cout << current << " ";

            for (int neighbor : g[current]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.push_back(neighbor); 
                }
            }
        }
        cout << "\n";
    }
    /*
6 5
4 1
1 2
5 3
0 5
3 4
4
0
3
1
2
*/
}
//Hw 2 :Problem 5
void solve5() {
    //print_paths_len_2
    int n,e;
    cin >> n >> e;
    vector<vector<int>> g(n+1);
    while(e--){ 
        int from ,to ; 
        cin >> from >> to ;
        g[from].push_back(to);
    }
    
    for(int i = 0 ; i <(int) g.size() ; i++){
        for(int j = 0 ; j <(int) g[i].size() ; j++){
            for(int k = 0 ; k <(int) g[g[i][j]].size() ; k++){
                cout << i << " " << g[i][j] << " " << g[g[i][j]][k] << endl;
            }
        }
    }

}
int main(){
    //solve();
    //solve2();
    //solve3();
    //solve4();
    //solve5();
    return 0;
}