#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;
}
}