/////////************** GRAPHS IN ADC++ **********////////////////
 
/// graphs are combination of nodes and edges 
// nodes = entity in which data is stored
// edges = connecting line which connect the nodes 
// degree = no of edges connected
 
 
 
////// types of graphs
 
// undirected graph = arrow will not be provided ... (v---u == u--v)
 
// directed graph = arrow will  be provided ... (v---u != u--v)
 
// they're two type of degree in directed 
// indegree = edges coming inside  my way  
// outdegree = edges coming out of  way  
 
// wieghted graph = theyre are wieghted writeen on edges(like numbers) default wieght is 1 
 
/// path = squence of nodes reaching (nodes written will not repeat)
 
// cyclic graph = when we create a path in which we reach the node which we written in previous order also. (like a-b-c-d and we d-a this cyclic graph)
 
/// TYPES OF REPRESENATATION 
 
/// i) adjacency matrix 
///  in this 2d matrix is made....
/// space complexity = O(n^2)
 
/// ii) adjacency list 
// in this we write the node connected with one and another in the form of list.
 
 
 
#include <iostream>
#include <unordered_map>
#include <list>
template <typename T>
using namespace std;
 
class graph {
public:
    unordered_map<T, list<T>> adj; // here we mapping a number with another number 
 
    void addEdge(T u, T v, bool direction) { // u and v are edges and bool for undirected and directed graph 
        // direction = 0 -> undirected graph
        // direction = 1 -> directed graph
 
        // creating an edge from u to v 
        adj[u].push_back(v); // created 
        if (direction == 0) { // checking directed or undirected 
            adj[v].push_back(u); // corrected from push.back to push_back
        }
    }
 
    void printAdjList() { // Removed the duplicate declaration
        for (auto i : adj) {
            cout << i.first << " -> ";
            for (auto j : i.second) {
                cout << j << ", ";
            }
            cout << endl; // Move to the next line after printing the list for a node
        }
    }
};
 
int main() {
    int n;
    cout << "Enter the number of nodes: " << endl;
    cin >> n;
 
    int m;
    cout << "Enter the number of edges: " << endl;
    cin >> m;
 
    graph g;
 
    for (int i = 0; i < m; i++) {
        int u, v;
        cout << "Enter edge (u v): "; // Prompt for edge input
        cin >> u >> v;
 
        // Ask the user for the type of graph
        int direction;
        cout << "Is the graph directed (1) or undirected (0)? ";
        cin >> direction;
 
        // creation of graph based on user input
        g.addEdge(u, v, direction);
    }
 
    // printing graph 
    g.printAdjList();
 
    return 0;
}