Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define se second
- #define fi first
- #define forn(i, n) for (int i = 0; i < n; i++)
- #define sz(a) (int)a.size()
- #define mp make_pair
- typedef long long ll;
- #ifdef LOCAL
- #define LASSERT(X) assert(X)
- #else
- #define LASSERT(X) {}
- #endif
- template <typename T>
- T input() {
- T res;
- cin >> res;
- LASSERT(cin);
- return res;
- }
- template <typename IT>
- void input_seq(IT b, IT e) {
- std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
- }
- #define SZ(vec) int((vec).size())
- #define ALL(data) data.begin(),data.end()
- #define RALL(data) data.rbegin(),data.rend()
- #define TYPEMAX(type) std::numeric_limits<type>::max()
- #define TYPEMIN(type) std::numeric_limits<type>::min()
- void no() {
- cout << "Impossible\n";
- exit(0);
- }
- vector<pair<int, int>> edges;
- vector<vector<pair<int, int>>> graph;
- vector<char> has;
- string ans;
- const char* trash = "HT";
- vector<int> dfs(vector<char>& used, int v, int id) {
- used[v] = 1;
- vector<int> cur;
- bool hs = false;
- if (SZ(graph[v]) % 2 == 1)
- hs = true;
- auto kek_in = [&](vector<int> vv) {
- if (not hs) {
- cur = vv;
- hs = 1;
- } else {
- std::reverse(ALL(vv));
- int col = 0;
- for (int elem: cur) {
- has[edges[elem].first] |= (1 << col);
- has[edges[elem].second] |= (1 << col);
- ans[elem] = trash[col];
- col = 1 - col;
- }
- for (int elem: vv) {
- has[edges[elem].first] |= (1 << col);
- has[edges[elem].second] |= (1 << col);
- ans[elem] = trash[col];
- col = 1 - col;
- }
- hs = false;
- cur.clear();
- }
- };
- for (auto u: graph[v])
- if (not used[u.first]) {
- auto tmp = dfs(used, u.first, u.second);
- if (not tmp.empty())
- kek_in(tmp);
- }
- if (hs) {
- cur.push_back(id);
- return cur;
- }
- return vector<int> {};
- }
- struct kek_t {
- int a;
- int id;
- int b;
- };
- void kukarek(vector<char>& usd, vector<vector<pair<int,int>>>& gr, int v, vector<kek_t>& lst) {
- while (not gr[v].empty()) {
- if (usd[gr[v].back().second]) {
- gr[v].pop_back();
- continue;
- }
- usd[gr[v].back().second] = true;
- int to = gr[v].back().first;
- int id = gr[v].back().second;
- gr[v].pop_back();
- kukarek(usd, gr, to, lst);
- lst.push_back(kek_t {to, id, v});
- }
- }
- int main() {
- iostream::sync_with_stdio(0), cin.tie(0), cout.tie(0);
- int n = input<int>();
- int m = input<int>();
- graph.resize(n);
- edges.resize(m);
- for (int i = 0; i != m; ++i) {
- int a = input<int>() - 1;
- int b = input<int>() - 1;
- graph[a].emplace_back(b, i);
- graph[b].emplace_back(a, i);
- edges[i] = {a, b};
- }
- for (int i = 0; i != m; ++i)
- ans += '_';
- for (int i = 0; i != n; ++i)
- if (graph[i].empty())
- no();
- vector<char> used(n, false);
- has.resize(n, 0);
- for (int i = 0; i != n; ++i)
- if (not used[i]) {
- dfs(used, 0, -1);
- }
- vector<vector<pair<int, int>>> gr(n);
- for (int i = 0; i != m; ++i)
- if (ans[i] == '_') {
- gr[edges[i].first].emplace_back(edges[i].second, i);
- gr[edges[i].second].emplace_back(edges[i].first, i);
- }
- vector<int> deg(n);
- for (int i = 0; i != n; ++i) {
- deg[i] = SZ(gr[i]);
- assert(gr[i].size() % 2 == 0);
- }
- vector<char> usd(m, false);
- for (int v = 0; v != n; ++v)
- if (not gr[v].empty()) {
- vector<kek_t> lst;
- kukarek(usd, gr, v, lst);
- int init_col = 0;
- if (SZ(lst) % 2 == 1) {
- int off = -1;
- for (int i = 0; i != SZ(lst); ++i) {
- if (has[lst[i].a] or deg[lst[i].a] >= 4) {
- off = i;
- break;
- }
- }
- if (off == -1)
- no();
- std::rotate(lst.begin(), lst.begin() + off, lst.end());
- init_col = (has[lst[0].a] & 2 ? 0 : 1);
- }
- for (auto elem: lst) {
- ans[elem.id] = trash[init_col];
- has[elem.a] |= (1 << init_col);
- has[elem.b] |= (1 << init_col);
- init_col ^= 1;
- }
- }
- for (int i = 0; i != n; ++i)
- if (has[i] != 3)
- no();
- cout << ans << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement