#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;
}
 

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8v4pyFIEFjY2VwdGVkCgpjbGFzcyBFZGdlewpwdWJsaWM6CiAgICBpbnQgdG8gLGNvc3Q7Cn07CnVzaW5nIEdSQVBIMiA9IHZlY3Rvcjx1bm9yZGVyZWRfc2V0PGludD4+Owp1c2luZyBHUkFQSCA9IHZlY3Rvcjx2ZWN0b3I8RWRnZT4+OwoKdm9pZCBhZGRfZWRnZShHUkFQSCAmZ3JhcGggLCBpbnQgZnJvbSAsIGludCB0byAsaW50IGNvc3QpewogICAgZ3JhcGhbZnJvbV0ucHVzaF9iYWNrKHt0byxjb3N0fSk7CiAgICAvL2dyYXBoW3RvXS5wdXNoX2JhY2soe2Zyb20sY29zdH0pOwp9Cgp2b2lkIHByaW50X2dyYXBoKEdSQVBIICZncmFwaCl7CiAgICBmb3IoaW50IGkgPSAxIDsgaSA8IGdyYXBoLnNpemUoKSA7IGkrKyl7CiAgICAgICAgY291dCA8PCBpIDw8ICIgOiAiOwogICAgICAgIGZvcihhdXRvIGogOiBncmFwaFtpXSl7CiAgICAgICAgICAgIGNvdXQgPDwgai50byA8PCAiICIgPDwgai5jb3N0IDw8ICIgIjsKICAgICAgICB9CiAgICAgICAgY291dCA8PCBlbmRsOwogICAgfQp9CgovL0h3IDIgOiBQcm9sZW0gMQp2b2lkIHNvbHZlKCkgewogICAgaW50IG4sZTsKICAgIGNpbiA+PiBuID4+IGU7CgogICAgdW5vcmRlcmVkX21hcDxzdHJpbmcsIHZlY3RvcjxwYWlyPHN0cmluZywgaW50Pj4+IGc7CiAgICBzZXQ8c3RyaW5nPiBub2RlczsKCiAgICB3aGlsZSAoZS0tKSB7CiAgICAgICAgc3RyaW5nIGZyb20sIHRvOwogICAgICAgIGludCBjb3N0OwogICAgICAgIGNpbiA+PiBmcm9tID4+IHRvID4+IGNvc3Q7CiAgICAgICAgZ1tmcm9tXS5wdXNoX2JhY2soe3RvLCBjb3N0fSk7CiAgICAgICAgbm9kZXMuaW5zZXJ0KGZyb20pOwogICAgICAgIG5vZGVzLmluc2VydCh0byk7CiAgICB9CgogICAgZm9yIChjb25zdCBhdXRvICZub2RlIDogbm9kZXMpIHsKICAgICAgICBhdXRvICZlZGdlcyA9IGdbbm9kZV07CiAgICAgICAgc29ydChlZGdlcy5iZWdpbigpLCBlZGdlcy5lbmQoKSwgW10oY29uc3QgYXV0byAmYSwgY29uc3QgYXV0byAmYikgewogICAgICAgICAgICBpZiAoYS5maXJzdCA9PSBiLmZpcnN0KQogICAgICAgICAgICAgICAgcmV0dXJuIGEuc2Vjb25kIDwgYi5zZWNvbmQ7CiAgICAgICAgICAgIHJldHVybiBhLmZpcnN0IDwgYi5maXJzdDsKICAgICAgICB9KTsKICAgICAgICBjb3V0IDw8IlxuIjsKICAgICAgICBpZihlZGdlcy5zaXplKCkgPT0gMCkgY29udGludWU7IAogICAgICAgIGNvdXQgPDwiRmxpZ2h0cyBGcm9tICI8PCBub2RlIDw8ICIgOiAiIDw8ICdcbic7CiAgICAgICAgZm9yIChjb25zdCBhdXRvICZlZGdlIDogZWRnZXMpIHsKICAgICAgICAgICAgY291dCA8PHNldHcoMTApPDwiVG8gIjw8IGVkZ2UuZmlyc3QgPDwgIiB3aXRoIGNvc3QgOiAiIDw8IGVkZ2Uuc2Vjb25kIDw8IGVuZGw7CiAgICAgICAgfQogICAgICAgIGNvdXQgPDwgZW5kbDsKICAgIH0KfQp2b2lkIGFkZF9lZGdlMihHUkFQSCAmZ3JhcGgsIGludCBmcm9tLCBpbnQgdG8sIGludCBjb3N0KSB7CiAgICBncmFwaFtmcm9tXS5wdXNoX2JhY2soe3RvLCBjb3N0fSk7CiAgICAKfQoKdm9pZCBwcmludF9ncmFwaDIoY29uc3QgR1JBUEggJmdyYXBoLCBjb25zdCB2ZWN0b3I8c3RyaW5nPiAmaW5kZXhfdG9fbmFtZSkgewogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBncmFwaC5zaXplKCk7IGkrKykgewogICAgICAgIGlmIChncmFwaFtpXS5lbXB0eSgpKSBjb250aW51ZTsKCiAgICAgICAgY291dCA8PCAiRmxpZ2h0cyBmcm9tICIgPDwgaW5kZXhfdG9fbmFtZVtpXSA8PCAiOlxuIjsKICAgICAgICBmb3IgKGNvbnN0IGF1dG8gJmVkZ2UgOiBncmFwaFtpXSkgewogICAgICAgICAgICBjb3V0IDw8IHNldHcoMTApIDw8ICJUbyAiIDw8IGluZGV4X3RvX25hbWVbZWRnZS50b10gPDwgIiB3aXRoIGNvc3QgIiA8PCBlZGdlLmNvc3QgPDwgJ1xuJzsKICAgICAgICB9CiAgICAgICAgY291dCA8PCBlbmRsOwogICAgfQp9CgovL0h3IDIgOiBQcm9sZW0gMgp2b2lkIHNvbHZlMigpIHsKICAgIGludCBuLCBlOwogICAgY2luID4+IG4gPj4gZTsKCiAgICBtYXA8c3RyaW5nLCBpbnQ+IG5hbWVfdG9faW5kZXg7CiAgICB2ZWN0b3I8c3RyaW5nPiBpbmRleF90b19uYW1lOwogICAgaW50IGlkeCA9IDA7CgogICAgR1JBUEggZyhuKTsgCgogICAgd2hpbGUgKGUtLSkgewogICAgICAgIHN0cmluZyBmcm9tLCB0bzsKICAgICAgICBpbnQgY29zdDsKICAgICAgICBjaW4gPj4gZnJvbSA+PiB0byA+PiBjb3N0OwoKICAgICAgICBpZiAobmFtZV90b19pbmRleC5maW5kKGZyb20pID09IG5hbWVfdG9faW5kZXguZW5kKCkpIHsKICAgICAgICAgICAgbmFtZV90b19pbmRleFtmcm9tXSA9IGlkeCsrOwogICAgICAgICAgICBpbmRleF90b19uYW1lLnB1c2hfYmFjayhmcm9tKTsKICAgICAgICB9CgogICAgICAgIGlmIChuYW1lX3RvX2luZGV4LmZpbmQodG8pID09IG5hbWVfdG9faW5kZXguZW5kKCkpIHsKICAgICAgICAgICAgbmFtZV90b19pbmRleFt0b10gPSBpZHgrKzsKICAgICAgICAgICAgaW5kZXhfdG9fbmFtZS5wdXNoX2JhY2sodG8pOwogICAgICAgIH0KCiAgICAgICAgaW50IHUgPSBuYW1lX3RvX2luZGV4W2Zyb21dOwogICAgICAgIGludCB2ID0gbmFtZV90b19pbmRleFt0b107CgogICAgICAgIGFkZF9lZGdlMihnLCB1LCB2LCBjb3N0KTsKICAgIH0KCiAgICBwcmludF9ncmFwaDIoZywgaW5kZXhfdG9fbmFtZSk7Cn0KLy9IdyAyIDogUHJvbGVtIDMKdm9pZCBzb2x2ZTMoKSB7CiAgICBpbnQgcixjOwogICAgY2luID4+IHIgPj4gYzsKICAgIGludCBpbWdbcl1bY10gPSB7MH07CiAgICAKICAgIGludCB2YWwgPTA7CiAgICBmb3IoaW50IGkgPSAwIDsgaSA8IHIgOyBpKyspewogICAgICAgIGZvcihpbnQgaiA9IDAgOyBqIDwgYyA7IGorKyl7CiAgICAgICAgICAgIGltZ1tpXVtqXSA9IHZhbCsrOwogICAgICAgIH0KICAgIH0KICAgIAogICAgdmVjdG9yPHZlY3Rvcjx2ZWN0b3I8aW50Pj4+IG5laWdoYm9ycyhyLCB2ZWN0b3I8dmVjdG9yPGludD4+KGMpKTsKICAgIAogICAgZm9yKGludCBpID0gMCA7IGkgPCByIDsgaSsrKXsKICAgICAgICBmb3IoaW50IGogPSAwIDsgaiA8IGMgOyBqKyspewogICAgICAgICAgICBpZihpID4gMCkgbmVpZ2hib3JzW2ldW2pdLnB1c2hfYmFjayhpbWdbaS0xXVtqXSk7CiAgICAgICAgICAgIGlmKGkgPCByLTEpIG5laWdoYm9yc1tpXVtqXS5wdXNoX2JhY2soaW1nW2krMV1bal0pOwogICAgICAgICAgICBpZihqID4gMCkgbmVpZ2hib3JzW2ldW2pdLnB1c2hfYmFjayhpbWdbaV1bai0xXSk7CiAgICAgICAgICAgIGlmKGogPCBjLTEpIG5laWdoYm9yc1tpXVtqXS5wdXNoX2JhY2soaW1nW2ldW2orMV0pOwogICAgICAgIH0KICAgIH0KCiAgICBmb3IoaW50IGkgPSAwIDsgaSA8IHIgOyBpKyspewogICAgICAgIGZvcihpbnQgaiA9IDAgOyBqIDwgYyA7IGorKyl7CiAgICAgICAgICAgIGNvdXQgPDwiTm9kZSA6ICI8PCBpbWdbaV1bal0gPDwgIiBoYXMgbmVpZ2hib3JzIDogIjsKICAgICAgICAgICAgZm9yKGF1dG8geCA6IG5laWdoYm9yc1tpXVtqXSl7CiAgICAgICAgICAgICAgICBjb3V0IDw8IHggPDwgIiAiOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGNvdXQgPDwgZW5kbDsKICAgICAgICB9CiAgICB9Cn0KLy9IdyAyIDpQcm9sZW0gNAp2b2lkIHNvbHZlNCgpIHsKICAgIGludCBuLCBlOwogICAgY2luID4+IG4gPj4gZTsKICAgIGxpc3Q8aW50PiBnW25dOyAKCiAgICB3aGlsZSAoZS0tKSB7CiAgICAgICAgaW50IGZyb20sIHRvOwogICAgICAgIGNpbiA+PiBmcm9tID4+IHRvOwogICAgICAgIGdbZnJvbV0ucHVzaF9iYWNrKHRvKTsKICAgIH0KCiAgICBpbnQgcTsKICAgIGNpbiA+PiBxOwogICAgd2hpbGUgKHEtLSkgewogICAgICAgIGludCBub2RlOwogICAgICAgIGNpbiA+PiBub2RlOwoKICAgICAgICB2ZWN0b3I8Ym9vbD4gdmlzaXRlZChuLCBmYWxzZSk7CiAgICAgICAgbGlzdDxpbnQ+IHF1ZXVlOyAKICAgICAgICBxdWV1ZS5wdXNoX2JhY2sobm9kZSk7CiAgICAgICAgdmlzaXRlZFtub2RlXSA9IHRydWU7CgogICAgICAgIHdoaWxlICghcXVldWUuZW1wdHkoKSkgewogICAgICAgICAgICBpbnQgY3VycmVudCA9IHF1ZXVlLmZyb250KCk7CiAgICAgICAgICAgIHF1ZXVlLnBvcF9mcm9udCgpOyAKCiAgICAgICAgICAgIGNvdXQgPDwgY3VycmVudCA8PCAiICI7CgogICAgICAgICAgICBmb3IgKGludCBuZWlnaGJvciA6IGdbY3VycmVudF0pIHsKICAgICAgICAgICAgICAgIGlmICghdmlzaXRlZFtuZWlnaGJvcl0pIHsKICAgICAgICAgICAgICAgICAgICB2aXNpdGVkW25laWdoYm9yXSA9IHRydWU7CiAgICAgICAgICAgICAgICAgICAgcXVldWUucHVzaF9iYWNrKG5laWdoYm9yKTsgCiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgY291dCA8PCAiXG4iOwogICAgfQogICAgLyoKNiA1CjQgMQoxIDIKNSAzCjAgNQozIDQKNAowCjMKMQoyCiovCn0KLy9IdyAyIDpQcm9ibGVtIDUKdm9pZCBzb2x2ZTUoKSB7CiAgICAvL3ByaW50X3BhdGhzX2xlbl8yCiAgICBpbnQgbixlOwogICAgY2luID4+IG4gPj4gZTsKICAgIHZlY3Rvcjx2ZWN0b3I8aW50Pj4gZyhuKzEpOwogICAgd2hpbGUoZS0tKXsgCiAgICAgICAgaW50IGZyb20gLHRvIDsgCiAgICAgICAgY2luID4+IGZyb20gPj4gdG8gOwogICAgICAgIGdbZnJvbV0ucHVzaF9iYWNrKHRvKTsKICAgIH0KICAgIAogICAgZm9yKGludCBpID0gMCA7IGkgPChpbnQpIGcuc2l6ZSgpIDsgaSsrKXsKICAgICAgICBmb3IoaW50IGogPSAwIDsgaiA8KGludCkgZ1tpXS5zaXplKCkgOyBqKyspewogICAgICAgICAgICBmb3IoaW50IGsgPSAwIDsgayA8KGludCkgZ1tnW2ldW2pdXS5zaXplKCkgOyBrKyspewogICAgICAgICAgICAgICAgY291dCA8PCBpIDw8ICIgIiA8PCBnW2ldW2pdIDw8ICIgIiA8PCBnW2dbaV1bal1dW2tdIDw8IGVuZGw7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cgp9CmludCBtYWluKCl7CiAgICAvL3NvbHZlKCk7CiAgICAvL3NvbHZlMigpOwogICAgLy9zb2x2ZTMoKTsKICAgIC8vc29sdmU0KCk7CiAgICAvL3NvbHZlNSgpOwogICAgcmV0dXJuIDA7Cn0K