Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <cmath>
- #include <algorithm>
- #include <vector>
- #include <set>
- #include <map>
- #include <stack>
- #include <queue>
- #include <cstdlib>
- #include <cstdio>
- #include <string>
- #include <cstring>
- #include <cassert>
- #include <utility>
- #include <iomanip>
- using namespace std;
- const int MAXN = 5 * 1050;
- struct edge {
- int to;
- bool used;
- bool bad;
- };
- int n;
- char ss[5];
- vector <edge> e;
- vector <int> g[MAXN];
- int in[MAXN], out[MAXN];
- vector <int> ans;
- int s = -1, t = -1;
- void dfs(int v) {
- for (int i = 0; i < (int) g[v].size(); i++) {
- int ind = g[v][i];
- int to = e[ind].to;
- if (e[ind].used)
- continue;
- e[ind].used = true;
- dfs(e[ind].to);
- }
- ans.push_back(v);
- }
- int main() {
- //assert(freopen("input.txt","r",stdin));
- //assert(freopen("output.txt","w",stdout));
- scanf("%d\n", &n);
- for (int i = 1; i <= n; i++) {
- gets(ss);
- int from = (int) ss[0] * 10 + (int) ss[1];
- int to = (int) ss[1] * 10 + (int) ss[2];
- //cerr << from << " " << to << endl;
- edge ed;
- ed.to = to;
- ed.used = false;
- e.push_back(ed);
- g[from].push_back( (int) e.size() - 1);
- out[from]++; in[to]++;
- }
- for (int i = 0; i < 3000; i++) {
- if ((in[i] % 2 == 0) && (out[i] % 2 == 0))
- continue;
- if (out[i] > in[i]) {
- if (s == -1) {
- s = i;
- }
- else {
- puts("NO");
- return 0;
- }
- }
- if (in[i] > out[i]) {
- if (t == -1) {
- t = i;
- }
- else {
- puts("NO");
- return 0;
- }
- }
- }
- if (s == -1 || t == -1) {
- puts("NO");
- return 0;
- }
- edge ed;
- ed.to = s;
- ed.bad = true;
- ed.used = true;
- e.push_back(ed);
- g[t].push_back( (int) e.size() - 1);
- dfs(s);
- puts("YES");
- int len = (int) ans.size();
- for (int i = 0; i < len; i++)
- cout << ans[i] << " ";
- cout << endl;
- int st = 0;
- for (int i = 0; i < len; i++) {
- if (i + 1 < len && ans[i] == t && ans[i + 1] == s) {
- st = i + 1;
- break;
- }
- }
- for (int j = 0; j < len - 1; j++) {
- int from = ans[(st + j) % len], to = ans[(st + j + 1) % len];
- if (j == 0) {
- putchar(from / 10);
- putchar(from % 10);
- }
- putchar(to % 10);
- }
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement