#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;


// DSU on steroids, basic version below
template<class ...Items>
class dsu
{
	vector<int> par, siz;
	tuple<Items...> items;

	template<size_t ...t>
	void merge(int a, int b, index_sequence<t...>)
	{
		(((get<t>(items))(a, b)), ...);

//		equivalent to:
//		(get<0>(items)) (a, b), // me
//		(get<1>(items)) (a, b); // sz
	}

public:
	explicit dsu(size_t n, Items... fn) : par(n, -1), siz(n, 1), items(fn...)
	{}

	int get_class(int v)
	{
		return par[v] == -1 ? v : par[v] = get_class(par[v]);
	}

	bool unite(int a, int b)
	{
		a = get_class(a);
		b = get_class(b);

		if (a == b)
			return false;

		if (siz[a] < siz[b])
			swap(a, b);

		par[b] = a;
		siz[a] += siz[b];

		merge(a, b, make_index_sequence<sizeof...(Items)>{});

		return true;
	}
};

/// Disjoint-set-union
class basic_dsu
{
	vector<int> par, siz, rk;

public:
	/// Constructor
	/// \param n the size
	explicit basic_dsu(size_t n = 0) : par(n, -1), siz(n, 1), rk(n, 0)
	{}

	/// Returns the representative of the connected component of the given vertex
	/// \param v the vertex, 0-indexed
	/// \return the answer
	int get_class(int v)
	{
		return par[v] == -1 ? v : par[v] = get_class(par[v]);
	}

	/// Unites connected components of the given vertices
	/// \param a, b the vertices, 0-indexed
	/// \return bool, representing whether the operation was nontrivial
	bool unite(int a, int b)
	{
		a = get_class(a);
		b = get_class(b);

		if (a == b)
			return false;

//		if (rk[a] < rk[b]) is also possible and fast
		if (siz[a] < siz[b])
			swap(a, b);

		par[b] = a;
		siz[a] += siz[b];

		if (rk[a] == rk[b])
			rk[a]++;

		return true;
	}
};


template<class T>
T &remax(T &x, const T &y)
{
	return x = max(x, y);
}


void solve(istream &cin = std::cin, ostream &cout = std::cout)
{
	int n, m; // the size and the number of queries

	cin >> n >> m;

	vector<int> max_el(n);
	iota(max_el.begin(), max_el.end(), 0);

	auto me = [&max_el](int a, int b)
	{
		remax(max_el[a], max_el[b]);
	};

	int cc = n;

	auto sz = [&cc](int, int)
	{
		cc--;
	};

	dsu dsu_fn(n, me, sz);
	dsu dsu_id(n);
	basic_dsu dsu_easy(n);

	for (int q = 0; q < m; q++)
	{
		int a, b;

		cin >> a >> b; // 1-indexed
		a--;
		b--;           // 0-indexed

		cout << (dsu_fn.unite(a, b) ? "YES" : "NO") << '\t';
		cout << (dsu_id.unite(a, b) ? "YES" : "NO") << '\t';
		cout << (dsu_easy.unite(a, b) ? "YES" : "NO") << endl;

		cout << max_el[dsu_fn.get_class(a)] + 1 << '\t' << cc << endl;
	}

	for (int i = 0; i < n; i++)
		cout << dsu_fn.get_class(i) << ' ';
	cout << endl;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cout << fixed;

#ifdef LOCAL
	auto st = chrono::steady_clock::now();

	ifstream fin("../input.txt");

	do
	{
		solve(fin);

		cout << "===" << endl;

		string str;
		while (getline(fin, str) && str != string(max(1, (int) str.size()), '='));
	} while (fin);

	cout << setprecision((int) floor(log10(chrono::steady_clock::duration::period::den)));
	cout << "clock: " << chrono::duration<double>(chrono::steady_clock::now() - st).count() << endl;
#else
	solve();
#endif

	return 0;
}