#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<bool> vis;
vector<vector<int>> adj;
bool find_edge(int u, int v)
{
    for (int i = 0; i < adj[u].size(); ++i)
    {
        if (adj[u][i] == v)
        {
            return true;
        }
    }
    return false;
}
void dfs(int u)
{
    if (vis[u])
        return;
    vis[u] = true;
    for (int i = 0; i < adj[u].size(); ++i)
        dfs(adj[u][i]);
}
void bfs(int u)//广度优先搜索
{
    vector<int> queue;
    int front = 0, rear = 0;
    queue.push_back(u);
    rear++;
    vis[u] = true;
    while (front < rear)
    {
        int v = queue[front];
        front++;
        for (int i = 0; i < adj[v].size(); ++i)
        {
            int w = adj[v][i];
            if (!vis[w])
            {
                queue.push_back(w);
                rear++;
                vis[w] = true;
            }
        }
    }
}
int main()
{
    cin >> n >> m;

    vis.resize(n + 1);
    adj.resize(n + 1);

    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    return 0;
}

//Prim算法
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> graph;
vector<bool> inMST;
vector<int> minEdge;
void Prim(int start)//时间复杂度：O(n^2)
{
    inMST[start] = true;
    for (int i = 1; i <= n; ++i)
    {
        minEdge[i] = graph[start][i];
    }
    for (int i = 1; i < n; ++i)
    {
        int u = -1;
        int minWeight = INT_MAX;
        for (int j = 1; j <= n; ++j)
        {
            if (!inMST[j] && minEdge[j] < minWeight)
            {
                minWeight = minEdge[j];
                u = j;
            }
        }
        if (u == -1)
            break; // 图不连通
        inMST[u] = true;
        for (int v = 1; v <= n; ++v)
        {
            if (!inMST[v] && graph[u][v] < minEdge[v])
            {   
                minEdge[v] = graph[u][v];
            }
        }
    }
}
//使用优先队列优化的prim算法
void Prim_Optimized(int start)//时间复杂度：O(m log n)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    inMST[start] = true;
    for (int i = 1; i <= n; ++i)
    {
        if (graph[start][i] < INT_MAX)
            pq.push({graph[start][i], i});
    }
    while (!pq.empty())
    {
        auto [weight, u] = pq.top();
        pq.pop();
        if (inMST[u])
            continue;
        inMST[u] = true;
        for (int v = 1; v <= n; ++v)
        {
            if (!inMST[v] && graph[u][v] < INT_MAX)
            {
                pq.push({graph[u][v], v});
            }
        }
    }
}

//使用邻接表存储的prim算法
#include <bits/stdc++.h>
using namespace std;
int n, m;
struct Edge
{
    int to;
    int weight;
};
vector<vector<Edge>> adj; // 邻接表，假设节点编号为 1..n

// 返回 MST 总权重，若图不连通则返回 -1；同时填 parent（父节点，root 的 parent = -1）
long long Prim_Simple(int start, vector<int> &parent)//时间复杂度：O(n^2)
{
    vector<bool> inMST(n + 1, false);
    vector<int> minEdge(n + 1, INT_MAX);
    parent.assign(n + 1, -1);

    minEdge[start] = 0;
    long long total = 0;
    for (int i = 1; i <= n; ++i)
    {
        int u = -1, best = INT_MAX;
        for (int v = 1; v <= n; ++v)
        {
            if (!inMST[v] && minEdge[v] < best)
            {
                best = minEdge[v];
                u = v;
            }
        }
        if (u == -1)
            return -1; // 不连通
        inMST[u] = true;
        total += (best == INT_MAX ? 0 : best);
        for (const auto &e : adj[u])
        {
            if (!inMST[e.to] && e.weight < minEdge[e.to])
            {
                minEdge[e.to] = e.weight;
                parent[e.to] = u;
            }
        }
    }
    return total;
}

// 使用优先队列的 Prim（更快），返回 MST 权重或 -1（不连通），并填 parent
long long Prim_Optimized(int start, vector<int> &parent)//时间复杂度：O(m log n)
{
    vector<bool> inMST(n + 1, false);
    vector<int> minEdge(n + 1, INT_MAX);
    parent.assign(n + 1, -1);

    using P = pair<int, int>; // {weight, node}
    priority_queue<P, vector<P>, greater<P>> pq;

    minEdge[start] = 0;
    pq.push({0, start});
    long long total = 0;
    int cnt = 0;

    while (!pq.empty())
    {
        auto [w, u] = pq.top();
        pq.pop();
        if (inMST[u])
            continue;
        inMST[u] = true;
        total += w;
        ++cnt;
        for (const auto &e : adj[u])
        {
            if (!inMST[e.to] && e.weight < minEdge[e.to])
            {
                minEdge[e.to] = e.weight;
                parent[e.to] = u;
                pq.push({e.weight, e.to});
            }
        }
    }
    if (cnt != n)
        return -1; // 不连通
    return total;
}

//Kruskal算法，时间复杂度：O(m log m)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100; // 假设最大节点数为 100
const int INF = 1e9;  // 用于表示无穷大
int n;                // 节点数
int graph[MAXN][MAXN]; // 邻接矩阵表示图
struct Edge {
    int u, v, weight;
    bool operator<(const Edge &other) const {
        return weight < other.weight;
    }
};
vector<Edge> edges; // 边列表
int parent[MAXN];  // 并查集父节点数组
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 路径压缩
    }
    return parent[x];
}
void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootY] = rootX; // 合并集合
    }
}
long long Kruskal() {
    // 初始化并查集
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
    // 按权重排序边
    sort(edges.begin(), edges.end());
    long long mstWeight = 0;
    int edgesUsed = 0;  // 记录已使用的边数
    for (const auto &edge : edges) {
        if (find(edge.u) != find(edge.v)) {
            unionSets(edge.u, edge.v);
            mstWeight += edge.weight;
            edgesUsed++;
            if (edgesUsed == n - 1) break; // 提前结束
        }
    }
    // 检查是否所有节点都连通
    if (edgesUsed != n - 1) return -1; // 图不连通
    return mstWeight;
}

#define MAX_EDGE 100
#define MAX_VERTEX 100
#define MAX 9999

struct VEdge {
    int fromV;  // 起始顶点
    int endV;    // 终止顶点
    int weight; // 边的权值
};

VEdge EdgeList[MAX_EDGE];
void GenSortEdge(MGraph G, VEdge EdgeList[]) {
    int k = 0, i, j;
    for (i = 0; i < G.vNum; i++) { // 边赋值
        for (j = i; j < G.vNum; j++) {
            if (G.arcs[i][j] != MAX) {
                EdgeList[k].fromV = i;
                EdgeList[k].endV = j;
                EdgeList[k].weight = G.arcs[i][j];
                k++;
            }
        }
    }
    for (i = 0; i < G.e - 1; i++) { // 边排序，这里用起泡排序，可以用其他排序方法替代
        for (j = i + 1; j < G.e; j++) {
            if (EdgeList[i].weight > EdgeList[j].weight) {
                VEdge t = EdgeList[i];
                EdgeList[i] = EdgeList[j];
                EdgeList[j] = t;
            }
        }
    }
}
void Kruskal(VEdge EdgeList[], int n, int e) {
    int vset[MAX_VERTEX];
    int i;
    for (i = 0; i < n; i++) {
        vset[i] = i; // 初始化vset
    }
    int k = 0, j = 0;
    while (k < n - 1) {
        int m = EdgeList[j].fromV, n_edge = EdgeList[j].endV;
        int sn1 = vset[m]; // m所属集合
        int sn2 = vset[n_edge]; // n所属集合
        if (sn1 != sn2) { // 两个顶点属于不同的集合
            printf("V%d -> V%d\n", m, n_edge);
            k++;
            for (i = 0; i < n; i++) {
                if (vset[i] == sn2) { // 集合编号为sn2的全部改为sn1
                    vset[i] = sn1;
                }
            }
        }
        j++;
    }
}

#include <bits/stdc++.h>
using namespace std;
const int MAXV = 100;
const int MAX_VALUE = INT_MAX / 4;
int i, j, k;
int dist[MAXV][MAXV];
string path[MAXV][MAXV];
struct MGraph {
    int vNum;
    string vertex[MAXV];
    int arc[MAXV][MAXV];
};

void Floyd(MGraph G)
{
    for (i = 0; i < G.vNum; i++)
        for (j = 0; j < G.vNum; j++)
        {
            dist[i][j] = G.arc[i][j];
            if (dist[i][j] != MAX_VALUE)
                path[i][j] = G.vertex[i] + G.vertex[j];
            else
                path[i][j] = "";
        }
    for (k = 0; k < G.vNum; k++)
        for (i = 0; i < G.vNum; i++)
            for (j = 0; j < G.vNum; j++)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = path[i][k] + path[k][j];
                }
}

#include <bits/stdc++.h>
using namespace std;
#define MAX_VERTEX 100
#define MAX 65535

typedef struct
{
    int arcs[MAX_VERTEX][MAX_VERTEX];
    int vNum;
} MGraph;

int FindMin(int Disk[], bool S[], int n)
{
    int k = 0, min = MAX;
    for (int i = 0; i < n; i++)
    {
        if (!S[i] && min > Disk[i])
        {
            min = Disk[i];
            k = i;
        }
    }
    if (min == MAX)
        return -1;
    return k;
}

void Print(int D[], int P[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << "V" << i << ": " << D[i] << "\tV" << i;
        int pre = P[i];
        while (pre != -1)
        {
            cout << "<-V" << pre;
            pre = P[pre];
        }
        cout << endl;
    }
}

void ShortPath(MGraph G, int v, int Disk[], int Path[])
{
    bool S[MAX_VERTEX];
    for (int i = 0; i < G.vNum; i++)
    {
        S[i] = false;
        Disk[i] = G.arcs[v][i];
        if (Disk[i] != MAX)
            Path[i] = v;
        else
            Path[i] = -1;
    }
    S[v] = true;
    Disk[v] = 0;
    for (int i = 0; i < G.vNum; i++)
    {
        if ((v = FindMin(Disk, S, G.vNum)) == -1)
            return;
        S[v] = true;
        for (int j = 0; j < G.vNum; j++)
        {
            if (!S[j] && (Disk[j] > G.arcs[v][j] + Disk[v]))
            {
                Disk[j] = G.arcs[v][j] + Disk[v];
                Path[j] = v;
            }
        }
    }
    Print(Disk, Path, G.vNum);
}

void ShortPath_Optimized(MGraph G, int v, int Disk[], int Path[]){
    bool S[MAX_VERTEX];
    for(int i = 0;i < G.vNum;i++){
        S[i] = false;
        Disk[i] = G.arcs[v][i];
        if(Disk[i] != MAX)
        Path[i] = v;
        else
        Path[i] = -1;
    }
    S[v] = true;
    Disk[v] = 0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    for(int i = 0;i < G.vNum;i++){
        pq.push({Disk[i],i});
    }
    while(!pq.empty()){
        auto p = pq.top();
        pq.pop();
        int u = p.second;
        if(S[u]) continue;
        S[u] = true;
        for(int j = 0;j < G.vNum;j++){
            if(!S[j] && (Disk[j] > G.arcs[u][j] + Disk[u])){
                Disk[j] = G.arcs[u][j] + Disk[u];
                Path[j] = u;
                pq.push({Disk[j],j});
            }
        }
    }
    Print(Disk,Path,G.vNum);
}