Problem: Problem F Pizza Delivery

Alyssa is a college student, living in New Tsukuba City. All the streets in the city are one-way. A new social experiment starting tomorrow is on alternative traffic regulation reversing the one-way directions of street sections. Reversals will be on one single street section between two adjacent intersections for each day; the directions of all the other sections will not change, and the reversal will be canceled on the next day.

Alyssa orders a piece of pizza everyday from the same pizzeria. The pizza is delivered along the shortest route from the intersection with the pizzeria to the intersection with Alyssa's house.

Altering the traffic regulation may change the shortest route. Please tell Alyssa how the social experiment will affect the pizza delivery route.

Input

The input consists of a single test case in the following format.


$n$ $m$
$a_1$ $b_1$ $c_1$
...
$a_m$ $b_m$ $c_m$


The first line contains two integers, $n$, the number of intersections, and $m$, the number of street sections in New Tsukuba City ($2 \leq n \leq 100 000, 1 \leq m \leq 100 000$). The intersections are numbered $1$ through $n$ and the street sections are numbered $1$ through $m$.

The following $m$ lines contain the information about the street sections, each with three integers $a_i$, $b_i$, and $c_i$ ($1 \leq a_i n, 1 \leq b_i \leq n, a_i \ne b_i, 1 \leq c_i \leq 100 000$). They mean that the street section numbered $i$ connects two intersections with the one-way direction from $a_i$ to $b_i$, which will be reversed on the $i$-th day. The street section has the length of $c_i$. Note that there may be more than one street section connecting the same pair of intersections.

The pizzeria is on the intersection 1 and Alyssa's house is on the intersection 2. It is guaranteed that at least one route exists from the pizzeria to Alyssa's before the social experiment starts.

Output

The output should contain $m$ lines. The $i$-th line should be

* HAPPY if the shortest route on the $i$-th day will become shorter,
* SOSO if the length of the shortest route on the $i$-th day will not change, and
* SAD if the shortest route on the $i$-th day will be longer or if there will be no route from the pizzeria to Alyssa's house.



Alyssa doesn't mind whether the delivery bike can go back to the pizzeria or not.

Sample Input 1


4 5
1 3 5
3 4 6
4 2 7
2 1 18
2 3 12


Sample Output 1


SAD
SAD
SAD
SOSO
HAPPY


Sample Input 2


7 5
1 3 2
1 6 3
4 2 4
6 2 5
7 5 6


Sample Output 2


SOSO
SAD
SOSO
SAD
SOSO


Sample Input 3


10 14
1 7 9
1 8 3
2 8 4
2 6 11
3 7 8
3 4 4
3 2 1
3 2 7
4 8 4
5 6 11
5 8 12
6 10 6
7 10 8
8 3 6


Sample Output 3


SOSO
SAD
HAPPY
SOSO
SOSO
SOSO
SAD
SOSO
SOSO
SOSO
SOSO
SOSO
SOSO
SAD






Example

Input

4 5
1 3 5
3 4 6
4 2 7
2 1 18
2 3 12


Output

SAD
SAD
SAD
SOSO
HAPPY

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) REP(i, 0, n)
#define REP(i, s, e) for (int i = (s); i < (int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for (int i = (int)(s - 1); i >= (int)(e); i--)
#define pb push_back
#define all(r) r.begin(), r.end()
#define rall(r) r.rbegin(), r.rend()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

template <typename T>
T chmax(T &a, const T &b) { return a = (a > b ? a : b); }
template <typename T>
T chmin(T &a, const T &b) { return a = (a < b ? a : b); }

#define DEBUG_MODE
#ifdef DEBUG_MODE
#define dump(x) cout << #x << " : " << x << " "
#define dumpL(x) cout << #x << " : " << x << '\n'
#define LINE cout << "line : " << __LINE__ << " "
#define LINEL cout << "line : " << __LINE__ << '\n'
#define dumpV(v)           \
    cout << #v << " : [";  \
    for (auto &t : v)      \
        cout << t << ", "; \
    cout << "]"            \
         << " "
#define dumpVL(v)          \
    cout << #v << " : [";  \
    for (auto &t : v)      \
        cout << t << ", "; \
    cout << "]" << endl
#define STOP assert(false)
#else
#define dump(x)
#define dumpL(x)
#define LINE
#define LINEL
#define dumpV(v)
#define dumpVL(v)
#define STOP assert(false)
#endif
#define mp make_pair

namespace std
{
template <class S, class T>
ostream &operator<<(ostream &out, const pair<S, T> &a)
{
    out << '(' << a.fi << ", " << a.se << ')';
    return out;
}
} // namespace std

//有向、無向グラフ共通クラス(隣接リスト)
struct Graph
{
    int n;
    using WEIGHT_TYPE = ll;
    static const WEIGHT_TYPE INF = 1e18;
    struct Edge
    {
        int to;
        WEIGHT_TYPE weight;
        int id;
    };
    struct Edge2
    {
        int from;
        int to;
        WEIGHT_TYPE weight;
        int id;
    };
    vector<vector<Edge>> es;
    Graph(int n) : n(n), es(n) {}

    // dijkstra O(E log V)
    vector<WEIGHT_TYPE> dijkstra(int s)
    {
        vector<WEIGHT_TYPE> d(n, INF);
        d[s] = 0;
        using P = pair<WEIGHT_TYPE, int>;
        priority_queue<P, vector<P>, greater<P>> q;
        q.push({0LL, s});
        while (!q.empty())
        {
            auto p = q.top();
            q.pop();
            int cur = p.se;
            auto cost = p.fi;
            if (d[cur] < p.fi)
                continue;
            for (auto &e : es[cur])
            {
                int to = e.to;
                auto dist = e.weight + cost;
                if (dist < d[to])
                {
                    d[to] = dist;
                    q.push({dist, to});
                }
            }
        }
        return d;
    }
    // warshall_floyd O(n^3)
    vector<vector<WEIGHT_TYPE>> warshall_floyd()
    {
        vector<vector<WEIGHT_TYPE>> d(n, vector<WEIGHT_TYPE>(n, INF));
        rep(i, n) d[i][i] = 0LL;
        rep(i, n) for (auto &&e : es[i])
        {
            int j = e.to;
            chmin(d[i][j], e.weight);
        }
        rep(k, n) rep(i, n) rep(j, n)
        {
            chmin(d[i][j], d[i][k] + d[k][j]);
        }
        return d;
    }
    // 頂点sから到達できるか
    vector<bool> getVisitable(int s)
    {
        vector<bool> ret(n);
        queue<int> q;
        q.push(s);
        ret[s] = true;
        while (!q.empty())
        {
            auto cur = q.front();
            q.pop();
            for (auto &&e : es[cur])
            {
                if (!ret[e.to])
                {
                    ret[e.to] = true;
                    q.push(e.to);
                }
            }
        }
        return ret;
    }
    //2部グラフ判定
    bool isBipartile()
    {
        vector<int> memo(n, -1);
        rep(i, n)
        {
            if (memo[i] != -1)
                continue;
            queue<int> q;
            q.push(i);
            memo[i] = 0;
            while (!q.empty())
            {
                auto v = q.front();
                q.pop();
                for (auto &&e : es[v])
                {
                    auto u = e.to;
                    if (memo[u] == -1)
                    {
                        memo[u] = !memo[v];
                        q.push(u);
                    }
                    else if (memo[u] == memo[v])
                    {
                        return false;
                    }
                }
            }
        }
        return true;
    }
};

// 無向グラフ
struct GraphUD : public Graph
{
    GraphUD(int n) : Graph(n) {}
    void add_edge(int from, int to, WEIGHT_TYPE weight, int id)
    {
        es[from].push_back({to, weight, id});
        es[to].push_back({from, weight, id});
    }
    vector<Edge2> getEdge2()
    {
        vector<Edge2> ret;
        rep(i, n) for (auto &&e : es[i])
        {
            if (i < e.to)
                ret.push_back({i, e.to, e.weight, e.id});
        }
        return ret;
    }
    // 橋の検出
    // http://nupioca.hatenadiary.jp/entry/2013/11/03/200006
    // Calculate bridges in a undirected graph.
    // Assume graph is connected and has no parallel edges or self-loops.
    vector<Edge2> getBridges()
    {
        int V = n;
        // res: bridges
        vector<Edge2> res;
        // assume at least the first vertex exists
        vector<int> low(V, -1); // lowest reacheable index
        vector<int> pre(V, -1); // pre-order index
        int count = 0;          // pre-order index counter

        // v: current node
        // from: parent node
        function<int(int, int)> dfs = [&](int v, int from) {
            pre[v] = count++;
            low[v] = pre[v];
            for (auto &&e : es[v])
            {
                int to = e.to;
                if (pre[to] == -1)
                {
                    // destination has not been visited
                    // visit destination and update low[v]
                    low[v] = min(low[v], dfs(to, v));
                    if (low[to] == pre[to])
                    {
                        // edge is not contained in a closed path -> bridge
                        res.push_back({v, to, e.weight, e.id});
                    }
                }
                else
                {
                    if (from == to)
                    {
                        // ignore a path to parent
                        continue;
                    }
                    low[v] = min(low[v], low[to]);
                }
            }
            return low[v];
        };

        dfs(0, -1); // start dfs from vertex 0

        return res;
    }
};

// 有向グラフ
struct GraphD : public Graph
{
    GraphD(int n) : Graph(n) {}
    void add_edge(int from, int to, WEIGHT_TYPE weight, int id)
    {
        es[from].push_back({to, weight, id});
    }
    vector<Edge2> getEdge2()
    {
        vector<Edge2> ret;
        rep(i, n) for (auto &&e : es[i])
        {
            ret.push_back({i, e.to, e.weight, e.id});
        }
        return ret;
    }
    GraphD getReverseGraph()
    {
        GraphD g(n);
        rep(i, n) for (auto &&e : es[i])
        {
            g.add_edge(e.to, i, e.weight, e.id);
        }
        return g;
    }
    vector<vector<int>> scc()
    {
        vector<vector<int>> res;
        vector<int> cmp(n);
        vector<int> vs;
        vector<vector<int>> r_es(n);
        rep(i, n) for (auto &&e : es[i])
        {
            int j = e.to;
            r_es[j].push_back(i);
        }

        vector<bool> used(n);
        function<void(int)> dfs = [&](int v) {
            used[v] = true;
            for (auto &&e : es[v])
            {
                int to = e.to;
                if (!used[to])
                    dfs(to);
            }
            vs.push_back(v);
        };
        function<void(int, int)> rdfs = [&](int v, int k) {
            used[v] = true;
            cmp[v] = k;
            for (auto &&to : r_es[v])
            {
                if (!used[to])
                    rdfs(to, k);
            }
        };

        fill(all(used), 0);
        vs.clear();
        for (int v = 0; v < n; v++)
        {
            if (!used[v])
                dfs(v);
        }
        fill(all(used), 0);
        int k = 0;
        for (int i = vs.size() - 1; i >= 0; i--)
        {
            if (!used[vs[i]])
                rdfs(vs[i], k++);
        }
        res.clear();
        res.resize(k);
        for (int i = 0; i < n; i++)
        {
            res[cmp[i]].push_back(i);
        }
        return res;
    }
    // bellmanFord 負閉路があるなら, dist[s] = INF | O(VE)
    vector<WEIGHT_TYPE> bellmanFord(int s)
    {
        vector<WEIGHT_TYPE> dist(n, INF);
        dist[s] = 0;
        auto es = getEdge2();
        rep(i, n)
        {
            for (auto &&e : es)
            {
                if (dist[e.to] > dist[e.from] + e.weight)
                {
                    dist[e.to] = dist[e.from] + e.weight;
                    if (i == n - 1)
                    {
                        dist[s] = INF;
                        return dist;
                    }
                }
            }
        }
        return dist;
    }
    // bellmanFord s->tの経路上に負閉路があるなら, dist[s] = INF | O(VE)
    vector<WEIGHT_TYPE> bellmanFord2(int s, int t)
    {
        vector<WEIGHT_TYPE> dist(n, INF);
        auto f1 = getVisitable(s);
        auto f2 = getReverseGraph().getVisitable(t);
        dist[s] = 0;
        auto es = getEdge2();
        rep(i, n)
        {
            for (auto &&e : es)
            {
                if (!(f1[e.from] && f2[e.to]))
                    continue;
                if (dist[e.to] > dist[e.from] + e.weight)
                {
                    dist[e.to] = dist[e.from] + e.weight;
                    if (i == n - 1)
                    {
                        dist[s] = INF;
                        return dist;
                    }
                }
            }
        }
        return dist;
    }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    GraphD g(n);
    vector<int> A(m), B(m), C(m);
    rep(i, m)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g.add_edge(a - 1, b - 1, c, i);
        A[i] = a - 1;
        B[i] = b - 1;
        C[i] = c;
    }
    auto x = g.dijkstra(0);
    auto y = g.getReverseGraph().dijkstra(1);

    vector<int> usedMinGraph(m);

    map<int, int> mp;

    rep(i, m)
    {
        int frm = A[i], to = B[i], cost = C[i];
        usedMinGraph[i] = ((x[frm] + cost == x[to]) && (y[to] + cost == y[frm]));
        if (usedMinGraph[i])
        {
            mp[frm] = 1;
            mp[to] = 1;
        }
    }
    {
        int cnt = 0;
        for (auto &p : mp)
            p.se = cnt++;
    }
    GraphUD f(mp.size());
    rep(i, m) if (usedMinGraph[i])
    {
        int u = A[i], v = B[i];
        f.add_edge(mp[u], mp[v], 1, i);
    }
    auto b = f.getBridges();
    // dumpL(b.size());
    vector<int> isBrdg(m);
    for (auto &&e2 : b)
    {
        isBrdg[e2.id] = true;
    }
    auto dist = x[1];
    rep(i, m)
    {
        if (usedMinGraph[i])
        {
            if (isBrdg[i])
                cout << "SAD" << '\n';
            else
                cout << "SOSO" << '\n';
        }
        else
        {
            int u = A[i], v = B[i], cost = C[i];
            if (x[v] + cost + y[u] < dist)
                cout << "HAPPY" << '\n';
            else
                cout << "SOSO" << '\n';
        }
    }
    // dumpVL(usedMinGraph);
    // dumpVL(isBrdg);
    // dumpVL(x);
    // dumpVL(y);
    return 0;
}