// BFS

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

const int N = 1e3;
vector<int> graph[N + 1];
vector<int> visited(N + 1, 0); // int visited[N]
// vector<int> level(N + 1, 0);   // int level[N]
vector<int> bfstraversal;

// Time Complexity = O(V+E)
void bfs(int source)
{
    queue<int> q;
    q.push(source);
    visited[source] = 1;

    while (!q.empty())
    {
        auto curr_ver = q.front();
        q.pop();
        bfstraversal.push_back(curr_ver);
        // cout<<curr_ver<<" ";
        for (auto child : graph[curr_ver])
        {
            if (visited[child] != 1)
            {
                q.push(child);
                visited[child] = 1;
                // level[child] = level[curr_ver] + 1;
            }
        }
    }
    for (auto node : bfstraversal)
    {
        cout << node << " ";
    }
    cout << endl;
}

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int source;
    cin >> source;

    bfs(source);

    // for (int i = 1; i <= n; i++)
    // {
    //     cout << i << ": " << level[i] << endl;
    // }

    return 0;
}


// DFS

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

const int N  = 1e3;
vector<int>graph[N+1];
vector<int>vis(N,0);

// Time Complexity = O(V+E)
void dfs(int vertex)
{
    //Take action on vertex after entering the vertex
    //if(vis[vertex]) return;
    cout<< vertex <<" ";
    vis[vertex]=1;
    for(auto child : graph[vertex])
    {
        //cout<<"Parent = " << vertex <<", Child = " << child <<endl;
        if(vis[child]==1) continue;
        //Take action on child befor entering the child node
        dfs(child);
        //Take action on child after exiting the child node
    }
    //Take action on vertex before exiting the vertex
    
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int u,v;
        cin>>u>>v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int source;
    cin>>source;

    dfs(source);
    
    return 0;
}

// DIJKSTRA

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

const int N = 1e3;
const int INF = 1e9;

vector<pair<int, int>> graph[N + 1];
vector<int> dist(N, INF);
vector<int> visited(N, 0);
vector<int> parent(N, -1);

// Time Complexity = O(V + ElogV)

// Multi Set Implementation
/*void dijkstra(int source)
{
    set<pair<double, int>> st; // double = wt, int = kon node er weight
    st.insert({0, source});
    dist[source] = 0;
    while (st.size() > 0)
    {
        auto node = *st.begin();
        int v = node.second;
        int dist_v = node.first;
        visited[v]=1;

        for (auto child : graph[v])
        {
            int child_v = child.first;
            int wt = child.second;
            if (dist[v] + wt < dist[child_v])
            //   new distance   current distance
            {
                dist[child_v] = dist[v] + wt;
                st.insert({dist[child_v], child_v});
            }
        }
    }
}*/

// Priority Queue Implementation
void dijkstra(int source)
{
    priority_queue<pair<double, int>> st; // double = weight
                                          //  int = kon node er weight

    st.push({0, source});
    dist[source] = 0;

    while (!st.empty())
    {
        auto node = st.top(); // minimum element
        int v = node.second;
        int v_dist = node.first;
        st.pop();
        // if (vis[v])
        //     continue;
        // vis[v] = 1;
        for (auto child : graph[v])
        {
            int child_v = child.first;
            int wt = child.second;

            if (dist[v] + wt < dist[child_v])
            {
                dist[child_v] = dist[v] + wt;
                st.push({dist[child_v], child_v});

                parent[child_v] = v; // Track parent for each node.
            }
        }
    }
}

void printPath(int source, int destination)
{
    if (destination == source)
    {
        cout << source << " ";
        return;
    }
    if (parent[destination] == -1)
    {
        cout << "No path from " << source << " to " << destination << endl;
        return;
    }
    printPath(source, parent[destination]);
    cout << destination << " ";
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v, wt;
        cin >> u >> v >> wt;

        graph[u].push_back({v, wt});
    }
    int source;
    cin >> source;

    dijkstra(source);

    for (int i = 1; i <= n; i++)
    {
        cout << "Shortest distance from " << source << " to " << i << " is: " << dist[i] << endl;
        printPath(source, i);
        cout<<endl;
    }

    return 0;
}

// BELLMAN FORD

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

const int N = 1e3;
const int INF = 1e9;

vector<pair<int, int>> graph[N + 1];
vector<int> dist(N, INF);
vector<int> visited(N, 0);
vector<int> parent(N, -1);

// Time Complexity = O(V + ElogV)

// Multi Set Implementation
/*void dijkstra(int source)
{
    set<pair<double, int>> st; // double = wt, int = kon node er weight
    st.insert({0, source});
    dist[source] = 0;
    while (st.size() > 0)
    {
        auto node = *st.begin();
        int v = node.second;
        int dist_v = node.first;
        visited[v]=1;

        for (auto child : graph[v])
        {
            int child_v = child.first;
            int wt = child.second;
            if (dist[v] + wt < dist[child_v])
            //   new distance   current distance
            {
                dist[child_v] = dist[v] + wt;
                st.insert({dist[child_v], child_v});
            }
        }
    }
}*/

// Priority Queue Implementation
void dijkstra(int source)
{
    priority_queue<pair<double, int>> st; // double = weight
                                          //  int = kon node er weight

    st.push({0, source});
    dist[source] = 0;

    while (!st.empty())
    {
        auto node = st.top(); // minimum element
        int v = node.second;
        int v_dist = node.first;
        st.pop();
        // if (vis[v])
        //     continue;
        // vis[v] = 1;
        for (auto child : graph[v])
        {
            int child_v = child.first;
            int wt = child.second;

            if (dist[v] + wt < dist[child_v])
            {
                dist[child_v] = dist[v] + wt;
                st.push({dist[child_v], child_v});

                parent[child_v] = v; // Track parent for each node.
            }
        }
    }
}

void printPath(int source, int destination)
{
    if (destination == source)
    {
        cout << source << " ";
        return;
    }
    if (parent[destination] == -1)
    {
        cout << "No path from " << source << " to " << destination << endl;
        return;
    }
    printPath(source, parent[destination]);
    cout << destination << " ";
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v, wt;
        cin >> u >> v >> wt;

        graph[u].push_back({v, wt});
    }
    int source;
    cin >> source;

    dijkstra(source);

    for (int i = 1; i <= n; i++)
    {
        cout << "Shortest distance from " << source << " to " << i << " is: " << dist[i] << endl;
        printPath(source, i);
        cout<<endl;
    }

    return 0;
}

//BMF NEGATIVE

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

const int N = 1e3;
const int INF = 1e9;

vector<vector<int>> graph;

void bellmanFord(int src, int n)
{
    vector<int> dist(n, INF);
    vector<int> parent(n, -1);
    int cycle_start = -1;

    dist[src] = 0;

    for (int i = 0; i < n - 1; ++i)
    {
        for (auto edge : graph)
        {
            int u = edge[0];
            int v = edge[1];
            int wt = edge[2];

            if (dist[u] != INF && dist[u] + wt < dist[v])
            {
                dist[v] = dist[u] + wt;
                parent[v] = u;
            }
        }
    }

    for (auto edge : graph)
    {
        int u = edge[0];
        int v = edge[1];
        int wt = edge[2];

        if (dist[u] != INF && dist[u] + wt < dist[v])
        {
            cycle_start = v;
            break;
        }
    }

    if (cycle_start != -1)
    {
        cout << "Graph contains a negative cycle." << endl;

        vector<int> cycle;
        vector<bool> visited(n, false);
        while (!visited[cycle_start])
        {
            cycle.push_back(cycle_start);
            visited[cycle_start] = true;
            cycle_start = parent[cycle_start];
        }

        for (int i = 0; i < cycle.size(); ++i)
        {
            if (cycle[i] == cycle_start)
            {
                cycle.erase(cycle.begin(), cycle.begin() + i);
                break;
            }
        }

        for (int vertex : cycle)
        {
            cout << vertex << " ";
        }
        cout << cycle_start << endl;
    }
    else
    {
        cout << "No negative cycle found." << endl;
    }
}

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; ++i)
    {
        int u, v, wt;
        cin >> u >> v >> wt;
        graph.push_back({u, v, wt});
    }

    int source;
    cin >> source;

    bellmanFord(source, n);

    /*
    //Printing Positive Cycle
    for(int i=0; i<m; i++)
    {
        graph[i][2] *= -1;
    }

    bellmanFord(source,n);
    */

    


    return 0;
}

// FLOYD WARSHALL

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

const int N = 1e3;
const int INF = 1e9;

int dist[N][N];

// Time Complexity = O(N^3)

int main()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i == j)
                dist[i][j] = 0;
            else
                dist[i][j] = INF;
        }
    }

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v, wt;
        cin >> u >> v >> wt;
        dist[u][v] = wt;
    }

    for (int k = 1; k <= n; k++) // k=level,
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }


    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (dist[i][j] == INF)
                cout << "I ";
            else
                cout << dist[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

// FLOYD WARSHALL NEGATIVE

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

const int N = 1e3;
const int INF = 1e9;

int dist[N][N];
int next_vertex[N][N];

int main()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i == j)
                dist[i][j] = 0;
            else
                dist[i][j] = INF;
        }
    }
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, wt;
        cin >> u >> v >> wt;
        dist[u][v] = wt;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (dist[i][j] != INF && i != j)
                next_vertex[i][j] = j;
            else
                next_vertex[i][j] = -1;
        }
    }
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (dist[i][k] != INF && dist[k][j] != INF)
                {
                    if (dist[i][j] > dist[i][k] + dist[k][j])
                    {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        next_vertex[i][j] = next_vertex[i][k];
                    }
                }
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (dist[i][i] < 0)
        {
            cout << "Graph contains a negative cycle." << endl;

            vector<int> cycle;
            int start = i;
            cycle.push_back(start);

            int current = next_vertex[start][start];
            while (current != start)
            {
                cycle.push_back(current);
                current = next_vertex[current][start];
            }
            cycle.push_back(start);

            for (auto vertex : cycle)
            {
                cout << vertex << " ";
            }
            cout << endl;
        }
    }

    // No negative cycle found
    // cout << "Graph doesn't contain a negative cycle." << endl;
    // for (int i = 1; i <= n; i++)
    // {
    //     for (int j = 1; j <= n; j++)
    //     {
    //         if (dist[i][j] == INF)
    //             cout << "-1 ";
    //         else
    //             cout << dist[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    return 0;
}

// PRIMS

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

const int n = 1e3;
vector<pair<int, int>> graph[n + 1];
vector<int> vis(n, 0);
vector<int> mstNodes;
vector<pair<int, int>> mstEdges; // To store edges in the MST
int cost;

int prims(int src)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, src});
    while (!pq.empty())
    {
        auto it = pq.top();
        pq.pop();
        int node = it.second;
        int wt = it.first;

        if (vis[node] == 1)
            continue;
        // add it to mst
        vis[node] = 1;
        mstNodes.push_back(node);
        cost += wt;

        for (auto it : graph[node])
        {
            int adjnode = it.first;
            int weight = it.second;

            if (!vis[adjnode])
            {
                pq.push({weight, adjnode});
                mstEdges.push_back({min(node, adjnode), max(node, adjnode)});
            }
        }
    }
    return cost;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v, wt;
        cin >> u >> v >> wt;
        graph[u].push_back({v, wt});
        graph[v].push_back({u, wt});
    }
    int src;
    cin >> src;

    cout << "Total Cost of MST: " << prims(src) << endl;

    cout << "Nodes that are in MST: ";
    for (auto it : mstNodes)
    {
        cout << it << " ";
    }
    cout<<endl;

    cout << "Edges in Minimum Spanning Tree:" << endl;
    for (auto edge : mstEdges)
    {
        cout << edge.first << " - " << edge.second << endl;
    }

    return 0;
}

// DP COIN CHANGE

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

const int n = 1e4;
int dp[n][n];

int func(int ind, int T, vector<int> &coins)
{
    if (ind == 0)
    {
        if (T % coins[0] == 0)
            return T / coins[0];
        else
            return 1e9;
    }
    if (dp[ind][T] != -1)
        return dp[ind][T];
    int notake = 0 + func(ind - 1, T, coins);

    int take = INT_MAX;
    if (coins[ind] <= T)
        take = 1 + func(ind, T - coins[ind], coins);

    int ans = min(notake, take);

    return dp[ind][T] = ans;
}

int minimumCoinChange(vector<int> &coin, int T)
{
    int n = coin.size();
    int ans = func(n - 1, T, coin);
    if (ans >= 1e9)
        return -1;

    return ans;
}

int main()
{
    memset(dp, -1, sizeof(dp));
    int n;
    cin >> n;
    vector<int> coins(n);
    for (int i = 0; i < n; i++)
    {
        cin >> coins[i];
    }
    int target;
    cin >> target;

    int ans = minimumCoinChange(coins, target);
    cout << ans;

    return 0;
}

// 01 KNAPSACK

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

const int n = 10000;
int wt[n], val[n];
int dp[n][n];

int knapsack(int ind, int W)
{
    if (ind == 0)
    {
        if (wt[0] <= W)
            return val[0];
        else
            return 0;
    }
    if (dp[ind][W] != -1)
        return dp[ind][W];
    int notake = 0 + knapsack(ind - 1, W);
    int take = INT_MIN;
    if (wt[ind] <= W)
        take = val[ind] + knapsack(ind - 1, W - wt[ind]);

    int ans = max(notake, take);

    return dp[ind][W] = ans;
}

int main()
{
    memset(dp, -1, sizeof(dp));
    int noOfitem, TotW;
    cin >> noOfitem >> TotW;
    for (int i = 0; i < noOfitem; i++)
    {
        cin >> wt[i] >> val[i];
    }
    int ans = knapsack(noOfitem - 1, TotW);
    cout << ans;
    return 0;
}

// TSP DP

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

vector<vector<int>> dp;
vector<vector<int>> dist; // adjacent matrix.
int n;                    // Number of Nodes.
int call(int S, int i)
{
    // All the nodes have been visited exactly once.

    if (S == ((1 << n) - 1))
    {
        return dist[i][1]; //Going back to origin from the current city
    }

    // Subtree has been calculated.
    if (dp[S][i] != -1)
        return dp[S][i];

    // Go to next unvisited node.
    int res = INT_MAX;
    for (int j = 0; j < n; j++)
    {
        if ((S & (1 << j)) == 0)
        {                                                       // if j'th node is unvisited.
            res = min(res, dist[i][j] + call(S | (1 << j), j)); // mark j'th node as visited.
        }
    }
    return dp[S][i] = res;
}
int main()
{
    cin >> n;
    dist.resize(n, vector<int>(n));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> dist[i][j];
        }
    }
    dp.resize(1 << n, vector<int>(n, -1));
    cout << call(1, 1) << endl;
}
/*
4
0 10 15 20
10 0 25 25
15 25 0 30
20 25 30 0
Output: 80
*/