#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <conio.h> //
#include <windows.h>

using namespace std;

size_t DFS(vector<vector<bool>> &graph);
size_t BFS(vector<vector<bool>> &graph);

void generate_tree(ULONGLONG v_count);


int main()
{
   setlocale(0, ""); //
   generate_tree(30000);

   ULONGLONG V, E;

   ifstream in("info.txt");
   if (!in.is_open())
   {
      cerr << "Не удалось открыть файл info";
      return -1;
   }
   in >> V >> E;


   in = ifstream("in.txt");
   if (!in.is_open())
   {
      cerr << "Не удалось открыть файл in";
      return -1;
   }


   vector<vector<bool>> graph(V);
   for (ULONGLONG i = 0; i < V; i++)
      graph[i].resize(V);

   for (ULONGLONG i = 0; i < E; i++)
   {
      ULONGLONG r, c;
      in >> r >> c;

      graph[r][c] = true;
      graph[c][r] = true;
   }


   ofstream out = ofstream("out.txt");

   clock_t s = clock(); //
   if (V - DFS(graph) == 0)
   {
      clock_t t = clock() - s; //
      cout << t / 1000 << "." << t % 1000 << "s" << endl; //

      if (E == V - 1)
         out << "Дерево." << endl;
      else out << "Не дерево: есть цикл." << endl;
   }
   else out << "Не дерево: компонент связности больше 1." << endl;

   return 0 * _getch(); //
}


size_t DFS(vector<vector<bool>> &graph)
{
   ULONGLONG x = 0, y = 0; //

   set<ULONGLONG> set;
   stack<ULONGLONG> stack;

   stack.push(0);

   while (!stack.empty())
   {
      y++; //
      bool down = false;

      int r = stack.top();
      set.insert(r);

      for (int c = r; c < graph.size() && !down; c++, x++) //
         if (down = graph[r][c] == 1 && set.count(c) == 0)
            stack.push(c);

      x--; //
      if (!down) stack.pop();
   }

   cout << "Итераций внешнего цикла: " << y << ", итераций вложенного цикла: " << x << endl; //

   return set.size();
}

size_t BFS(vector<vector<bool>> &graph)
{
   ULONGLONG x = 0, y = 0; //

   set<ULONGLONG> set;
   queue<ULONGLONG> queue;

   queue.push(0);

   while (!queue.empty())
   {
      y++; //
      ULONGLONG r = queue.front();

      set.insert(r);
      queue.pop();

      for (int c = 0; c < graph.size(); c++, x++)//
         if (graph[r][c] == 1 && set.count(c) == 0)
            queue.push(c);

      x--; //
   }

   cout << "Итераций внешнего цикла: " << y << ", итераций вложенного цикла: " << x << endl; //

   return set.size();
}

void generate_tree(ULONGLONG v_count)
{
   ofstream out("info.txt");
   out << v_count << ' ' << v_count - 1 << endl;

   out = ofstream("in.txt");

   ULONGLONG v_num = 0, dif = 1;
   for (ULONGLONG i = 0; i < v_count - 1; i++)
   {
      out << v_num << ' ' << dif++ << endl;
      v_num += dif % 2;
   }
}