//Một Graph vô hướng được coi là liên thông theo 2 cạnh khi nó vẫn duy trì trạng thái liên thông khi một cạnh bất kỳ bị hủy. Kiểm tra //xem graph hiện tại có phải là graph dạng liên thông 2 cạnh hay không

//Đầu vào: Dòng đầu tiên gồm số n và m đại biểu cho số đỉnh và cạnh. m dòng tiếp theo, mỗi dòng chứa hai đỉnh mà cạnh đó nối

//Đầu ra: True hoặc False đại biểu cho graph có thỏa mãn điều kiên hay không.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

// data structure to store graph edges
struct Edge {
    int src, dest;
};

class Graph
{
public:
    // construct a vector of vectors to represent an adjacency list
    vector<vector<int>> adjList;

    // Graph Constructor
    Graph(vector<Edge> const &edges, int N)
    {
        // resize the vector to N elements of type vector<int>
        adjList.resize(N);

        // add edges to the undirected graph
        for (auto &edge: edges)
        {
            adjList[edge.src].push_back(edge.dest);
            adjList[edge.dest].push_back(edge.src);
        }
    }
};

// Perform DFS on graph starting from vertex v and find
// all Bridges in the process
int DFS(Graph const &graph, int v, vector<bool> discovered,
                int arrival[], int parent, int &time, bool &econ)
{
    // set arrival time of vertex v
    arrival[v] = ++time;

    // mark vertex as discovered
    discovered[v] = true;

    // initialize arr to arrival time of vertex v
    int arr = arrival[v];

    // (v, w) forms an edge
    for (int w : graph.adjList[v])
    {
        // w is not discovered
        if (!discovered[w]) {
            arr = min(arr, DFS(graph, w, discovered,
                            arrival, v, time, econ));

        // w is discovered and w is not parent of v
        } else if (w != parent) {
            // If the vertex w is already discovered, that
            // means that there is a back edge starting
            // from v. Note that as discovered[u] is already
            // true, arrival[u] is already defined
            arr = min(arr, arrival[w]);
        }
    }

    // if value of arr remains unchanged i.e. it is equal
    // to the arrival time of vertex v and if v is not root
    // node, then (parent[v] -> v) forms a Bridge
    if (arr == arrival[v] && parent != -1)
        //cout << parent << ", " << v << '\n';
        econ=false;

    // we return the minimum arrival time
    return arr;
}

// 2-Edge Connectivity in a Graph
int main()
{
    // Number of nodes in the graph
    int N, M;
    cin >> N >> M;
    // vector of graph edges as per above diagram
    vector<Edge> edges;
    int s, d;
    for(int i=0; i<M; i++) {
        cin >> s >> d;
        Edge e = {s, d};
        edges.push_back(e);
    }
    // = { {0, 2}, {1, 2}, {2, 3}, {2, 4}, {3, 4}, {3, 5} }


    // create a graph from edges
    Graph graph(edges, N);

    // stores vertex is discovered or not
    vector<bool> discovered(N);

    // stores arrival time of a node in DFS
    int arrival[N];

    int start = 0, parent = -1, time = 0;

    bool econ = true;
    // As given graph is connected, DFS will cover every node
    DFS(graph, start, discovered, arrival, parent, time, econ);
    //bool all_node_discovered = all_of(discovered.begin(), discovered.end(), [](bool v) { return v; });
    //for(int i=0; i<N; i++) cout << discovered[i] << " ";
    if(econ) {cout << "True";} else {cout << "False";}

    return 0;
}