fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Macros
  5. #define pb push_back
  6. #define pf push_front
  7. #define ff first
  8. #define ss second
  9. #define all(v) v.begin(), v.end()
  10. #define rall(v) v.rbegin(), v.rend()
  11.  
  12. #define rep(i, x, n) for(int i = x; i < n; ++i)
  13. #define rrep(i, x, n) for(int i = x; i >= n; --i)
  14.  
  15. // Read and Print
  16. #define read(a, i, n) for(ll i = 0; i < n; ++i) cin >> a[i];
  17. #define print(a, i, n) for(ll i = 0; i < n; ++i){ cout << a[i] << " ";} cout << "\n";
  18.  
  19. // Typedefs
  20. typedef long long ll;
  21. typedef long double ld;
  22. typedef pair <ll, ll> pii;
  23.  
  24. typedef vector <ll> vi;
  25. typedef vector <vector <ll>> vvi;
  26.  
  27. // Constants
  28. const ll mxn = 1e5 + 5;
  29. const ll mod = 1e9 + 7;
  30.  
  31. // Fast IO
  32. void fast(){
  33. ios_base::sync_with_stdio(false);
  34. cin.tie(0); cout.tie(0);
  35. }
  36.  
  37. // Solve
  38.  
  39. vector <set <int>> adj(mxn);
  40. vector <int> in(mxn), out(mxn);
  41. vector <int> path;
  42.  
  43. void dfs(int root){
  44. while(adj[root].size()){
  45. int m = adj[root].size();
  46. int it = *adj[root].begin();
  47.  
  48. adj[root].erase(it);
  49. adj[it].erase(root);
  50. dfs(it);
  51. }
  52.  
  53. path.pb(root);
  54. }
  55.  
  56. void solve() {
  57.  
  58. int n, m;
  59. cin >> n >> m;
  60.  
  61. for(int i = 0; i < m; ++i){
  62. int u, v;
  63. cin >> u >> v;
  64. --u, --v;
  65.  
  66. adj[u].insert(v);
  67. adj[v].insert(u);
  68.  
  69. in[u]++, in[v]++, out[u]++, out[v]++;
  70. }
  71.  
  72. // print(in, i, n);
  73. // print(out, i, n);
  74.  
  75. bool ok = 1;
  76.  
  77. for(int i = 0; i < n; ++i){
  78. if(in[i] != out[i]){
  79. ok = 0; break;
  80. }
  81. if(in[i] % 2 == 1){
  82. ok = 0; break;
  83. }
  84. }
  85.  
  86. if(!ok) cout << "IMPOSSIBLE\n";
  87. else{
  88. dfs(0);
  89.  
  90. // print(path, i, path.size());
  91.  
  92. if(path.size() == m + 1){
  93. reverse(path.begin(), path.end());
  94. rep(i, 0, path.size()){
  95. cout << path[i] + 1 << " ";
  96. }
  97. cout << "\n";
  98. }
  99. else{
  100. cout << "IMPOSSIBLE\n";
  101. }
  102. }
  103. }
  104.  
  105. int main(){
  106.  
  107. // fast();
  108. solve();
  109.  
  110. return 0;
  111. }
Runtime error #stdin #stdout 0.04s 8768KB
stdin
Standard input is empty
stdout
Standard output is empty