Advertisement
konchin_shih

Mail Delivery

Aug 8th, 2022
909
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.21 KB | None | 0 0
  1. #include<iostream>
  2. #include<iomanip>
  3. #include<vector>
  4. #include<algorithm>
  5. #include<tuple>
  6. #include<functional>
  7. #include<numeric>
  8. #include<random>
  9. #include<unordered_map>
  10. #include<set>
  11. #include<map>
  12. #include<unordered_set>
  13. #include<cassert>
  14. #include<cmath>
  15. #include<queue>
  16. #include<stack>
  17. #include<sstream>
  18. // #define endl '\n'
  19. using namespace std;
  20. using ll=long long;
  21. using ull=unsigned long long;
  22. using ld=long double;
  23. using sstream=stringstream;
  24. template<typename T1,typename T2=T1> using P=pair<T1,T2>;
  25. template<typename T> using V=vector<T>;
  26. template<typename T> using F=function<T>;
  27. void _debug() {cerr << '\n';}
  28. template <typename A, typename... B>
  29. void _debug(A a, B... b) {cerr << a << ' ', _debug(b...);}
  30. #define debug(...) cerr << '(' << (#__VA_ARGS__) << ") : ", _debug(__VA_ARGS__)
  31. template<typename T>
  32. ostream& operator<<(ostream& os,const V<T>& v){
  33.     for(const auto& i:v)
  34.         os<<i<<' ';
  35.     return os;
  36. }
  37. template<typename T>
  38. ostream& operator<<(ostream& os,const unordered_set<T>& v){
  39.     for(const auto& i:v)
  40.         os<<i<<' ';
  41.     return os;
  42. }
  43. template<typename T1,typename T2>
  44. ostream& operator<<(ostream& os,const P<T1,T2>& p){
  45.     return os<<'('<<p.first<<','<<p.second<<") ";
  46. }
  47. mt19937 mt(hash<string>()(":poop:"));
  48. constexpr int inf=0x3f3f3f3f;
  49. constexpr ll infll=0x3f3f3f3f3f3f3f3f;
  50. constexpr int mod=1e9+7;
  51. inline void init(){
  52.    
  53. }
  54. inline void solve() {
  55.     int n,m;cin>>n>>m;
  56.     V<V<P<ll,int>>> e(n);
  57.     V<bool> vis(m,false);
  58.     V<int> out(n,0);
  59.     for(int i=0;i<m;i++){
  60.         int a,b;cin>>a>>b;a--,b--;
  61.         e[a].emplace_back(b,i);
  62.         e[b].emplace_back(a,i);
  63.         out[a]++,out[b]++;
  64.     }
  65.     if(!out[0]){
  66.         cout<<"IMPOSSIBLE"<<endl;
  67.         return;
  68.     }
  69.     for(auto i:out)
  70.         if(i&1){
  71.             cout<<"IMPOSSIBLE"<<endl;
  72.             return;
  73.         }
  74.     // debug(out);
  75.     V<int> ans{1};
  76.     F<void(int,int,int)> dfs=[&](int u,int v,int i){
  77.         if(vis[i]) return;
  78.         vis[i]=true;
  79.         for(auto [x,j]:e[v])
  80.             if(!vis[j]) dfs(v,x,j);
  81.         ans.emplace_back(u+1);
  82.     };
  83.     for(auto [v,i]:e[0])
  84.         dfs(0,v,i);
  85.     if((int)ans.size()!=m+1){
  86.         cout<<"IMPOSSIBLE"<<endl;
  87.         return;
  88.     }
  89.     for(auto i:ans)
  90.         cout<<i<<' ';
  91. }
  92. signed main(){
  93.     // cin.tie(nullptr)->sync_with_stdio(false);
  94.     signed T=1;
  95.     // cin>>T;
  96.     init();
  97.     while(T--)
  98.         solve();
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement