#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

int n, m; // n - кол-во вершин, m - кол-во рёбер
vector <vector <int>> g; // граф (в памяти компьютера будет храниться в виде списков смежности)
vector <bool> used;

void dfs(int v) {
    used[v] = true;
    for (int u : g[v])
        if (!used[u])
            dfs(u);
}

int main() {
    setlocale(LC_ALL, "rus");
    ifstream rd;
    rd.open("graph.txt");
    rd >> n >> m;
    g.resize(n);
    used.resize(n, false);
    for (int i = 0; i < m; i++) {
        int u, v;
        rd >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int st = 0;
    dfs(st);
    bool b = true;
    for (int i = 0; i < n && b; i++)
        if (!used[i]) {
            cout << "Граф НЕсвязный" << endl;
            b = false;
        }
    if (b)
        cout << "Граф связный";
    system("pause");
    return 0;
}