508D - Tanya and Password - CodeForces Solution

/* In the name of Allah */
// Welcome to the Soldier Side!
// Where there's no one here, but me...
#include<bits/stdc++.h>
using namespace std;

const int N = 4e5 + 5;
vector<int> result;
vector<int> adj[N];
int n, m, d[N];
string t[N];

int get_id(string s) {
	static map<string, int> mp;
	return !mp.count(s)? t[m] = s, mp[s] = m++: mp[s];
}

void dfs(int u) {
	while (!adj[u].empty()) {
		int v = adj[u].back();
		adj[u].pop_back();
		dfs(v);
	}
	result.push_back(u);
}

void read_input() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;

		int u = get_id(s.substr(0, 2));
		int v = get_id(s.substr(1));
		adj[u].push_back(v);
		d[u]++, d[v]--;
	}
}

void solve() {
	int cnt = 0;
	for (int u = 0; u < n; u++)
		if (d[u])
			cnt++;
	if (cnt > 2) {
		cout << "NO";
		exit(0);
	}

	for (int u = 0; u < m; u++)
		if (d[u] > 0) {
			if (d[u] > 1) {
				cout << "NO";
				exit(0);
			}

			dfs(u);
			return;
		}
	dfs(0);
}

void write_output() {
	if (result.size() < n + 1) {
		cout << "NO";
		return;
	}

	reverse(result.begin(), result.end());
	cout << "YES\n" << t[result[0]][0];
	for (int p: result)
		cout << t[p][1];
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), solve(), write_output();
	return 0;
}