Advertisement
Guest User

Untitled

a guest
Oct 19th, 2018
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define se second
  6. #define fi first
  7. #define forn(i, n) for (int i = 0; i < n; i++)
  8. #define sz(a) (int)a.size()
  9. #define mp make_pair
  10.  
  11. typedef long long ll;
  12.  
  13. #ifdef LOCAL
  14. #define LASSERT(X) assert(X)
  15. #else
  16. #define LASSERT(X) {}
  17. #endif
  18.  
  19. template <typename T>
  20. T input() {
  21.     T res;
  22.     cin >> res;
  23.     LASSERT(cin);
  24.     return res;
  25. }
  26.  
  27. template <typename IT>
  28. void input_seq(IT b, IT e) {
  29.     std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
  30. }
  31.  
  32. #define SZ(vec)         int((vec).size())
  33. #define ALL(data)       data.begin(),data.end()
  34. #define RALL(data)      data.rbegin(),data.rend()
  35. #define TYPEMAX(type)   std::numeric_limits<type>::max()
  36. #define TYPEMIN(type)   std::numeric_limits<type>::min()
  37.  
  38.  
  39. void no() {
  40.     cout << "Impossible\n";
  41.     exit(0);
  42. }
  43.  
  44. vector<pair<int, int>> edges;
  45. vector<vector<pair<int, int>>> graph;
  46. vector<char> has;
  47.  
  48. string ans;
  49. const char* trash = "HT";
  50.  
  51. vector<int> dfs(vector<char>& used, int v, int id) {
  52.     used[v] = 1;
  53.    
  54.     vector<int> cur;
  55.     bool hs = false;
  56.  
  57.     if (SZ(graph[v]) % 2 == 1)
  58.         hs = true;
  59.  
  60.     auto kek_in = [&](vector<int> vv) {
  61.         if (not hs) {
  62.             cur = vv;
  63.             hs = 1;
  64.         } else {
  65.             std::reverse(ALL(vv));
  66.            
  67.             int col = 0;
  68.             for (int elem: cur) {
  69.                 has[edges[elem].first] |= (1 << col);
  70.                 has[edges[elem].second] |= (1 << col);
  71.                
  72.                 ans[elem] = trash[col];
  73.                 col = 1 - col;
  74.             }
  75.  
  76.             for (int elem: vv) {
  77.                 has[edges[elem].first] |= (1 << col);
  78.                 has[edges[elem].second] |= (1 << col);
  79.  
  80.                 ans[elem] = trash[col];
  81.                 col = 1 - col;
  82.             }
  83.  
  84.  
  85.             hs = false;
  86.             cur.clear();
  87.         }
  88.     };
  89.    
  90.     for (auto u: graph[v])
  91.         if (not used[u.first]) {
  92.             auto tmp = dfs(used, u.first, u.second);
  93.  
  94.             if (not tmp.empty())
  95.                 kek_in(tmp);
  96.         }
  97.  
  98.     if (hs) {
  99.         cur.push_back(id);
  100.         return cur;
  101.     }
  102.  
  103.     return vector<int> {};
  104. }
  105.  
  106. struct kek_t {
  107.     int a;
  108.     int id;
  109.     int b;
  110. };
  111.  
  112. void kukarek(vector<char>& usd, vector<vector<pair<int,int>>>& gr, int v, vector<kek_t>& lst) {
  113.  
  114.     while (not gr[v].empty()) {
  115.         if (usd[gr[v].back().second]) {
  116.             gr[v].pop_back();
  117.             continue;
  118.         }
  119.  
  120.         usd[gr[v].back().second] = true;
  121.         int to = gr[v].back().first;
  122.         int id = gr[v].back().second;
  123.        
  124.         gr[v].pop_back();
  125.        
  126.         kukarek(usd, gr, to, lst);
  127.  
  128.         lst.push_back(kek_t {to, id, v});
  129.     }
  130. }
  131.  
  132. int main() {
  133.     iostream::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  134.  
  135.     int n = input<int>();
  136.     int m = input<int>();
  137.  
  138.     graph.resize(n);
  139.     edges.resize(m);
  140.     for (int i = 0; i != m; ++i) {
  141.         int a = input<int>() - 1;
  142.         int b = input<int>() - 1;
  143.  
  144.         graph[a].emplace_back(b, i);
  145.         graph[b].emplace_back(a, i);
  146.        
  147.         edges[i] = {a, b};
  148.     }
  149.  
  150.     for (int i = 0; i != m; ++i)
  151.         ans += '_';
  152.    
  153.     for (int i = 0; i != n; ++i)
  154.         if (graph[i].empty())
  155.             no();
  156.  
  157.     vector<char> used(n, false);
  158.     has.resize(n, 0);
  159.     for (int i = 0; i != n; ++i)
  160.         if (not used[i]) {
  161.             dfs(used, 0, -1);
  162.         }
  163.  
  164.     vector<vector<pair<int, int>>> gr(n);
  165.     for (int i = 0; i != m; ++i)
  166.         if (ans[i] == '_') {
  167.             gr[edges[i].first].emplace_back(edges[i].second, i);
  168.             gr[edges[i].second].emplace_back(edges[i].first, i);
  169.         }
  170.  
  171.     vector<int> deg(n);
  172.     for (int i = 0; i != n; ++i) {
  173.         deg[i] = SZ(gr[i]);
  174.         assert(gr[i].size() % 2 == 0);
  175.     }
  176.    
  177.     vector<char> usd(m, false);
  178.     for (int v = 0; v != n; ++v)
  179.         if (not gr[v].empty()) {
  180.             vector<kek_t> lst;
  181.            
  182.             kukarek(usd, gr, v, lst);
  183.  
  184.             int init_col = 0;
  185.             if (SZ(lst) % 2 == 1) {
  186.                 int off = -1;
  187.                 for (int i = 0; i != SZ(lst); ++i) {
  188.                     if (has[lst[i].a] or deg[lst[i].a] >= 4) {
  189.                         off = i;
  190.                         break;
  191.                     }
  192.                 }
  193.  
  194.                 if (off == -1)
  195.                     no();
  196.  
  197.                 std::rotate(lst.begin(), lst.begin() + off, lst.end());
  198.  
  199.                 init_col = (has[lst[0].a] & 2 ? 0 : 1);
  200.             }
  201.  
  202.             for (auto elem: lst) {
  203.                 ans[elem.id] = trash[init_col];
  204.                 has[elem.a] |= (1 << init_col);
  205.                 has[elem.b] |= (1 << init_col);
  206.  
  207.                 init_col ^= 1;
  208.             }
  209.         }
  210.  
  211.     for (int i = 0; i != n; ++i)
  212.         if (has[i] != 3)
  213.             no();
  214.  
  215.     cout << ans << "\n";
  216.    
  217.     return 0;
  218. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement