const int N = 2510;
int son[N][26], idx, w[N];
class MapSum {
public:
    /** Initialize your data structure here. */
    MapSum() {
        memset(son, 0, sizeof son);
        memset(w, 0, sizeof w);
        idx = 0;
    }

    void insert(string key, int val) {
        int p = 0;
        for (auto c: key) {
            int u = c - 'a';
            if (!son[p][u]) son[p][u] = ++ idx;
            p = son[p][u];
        }
        w[p] = val;
    }

    int sum(string prefix) {
        int p = 0, res = 0;
        for (auto c: prefix) {
            int u = c - 'a';
            if (son[p][u]) p = son[p][u];
            else return 0;
        }
        return dfs(p);
    }
    int dfs(int p) {
        int res = w[p];
        for (int i = 0; i < 26; i ++ )
            if (son[p][i])
                res += dfs(son[p][i]);
        return res;
    }
};

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum* obj = new MapSum();
 * obj->insert(key,val);
 * int param_2 = obj->sum(prefix);
 */

class MagicDictionary {
public:
    /** Initialize your data structure here. */
    struct Node {
        bool is_end;
        Node* son[26];
        Node() {
            is_end = false;
            memset(son, 0, sizeof son);
        }
    }*root;

    void insert(string w) {
        auto p = root;
        for (int i = 0; i < w.size(); i ++ ) {
            int idx = w[i] - 'a';
            if (!p->son[idx]) p->son[idx] = new Node();
            p = p->son[idx];
        }
        p->is_end = true;
    }

    MagicDictionary() {

    }

    void buildDict(vector<string> dictionary) {
        root = new Node();
        for (auto& w : dictionary) {
            insert(w);
        }
    }

    bool search(string w) {
        return dfs(w, 0, 1, root);
    }

    bool dfs(string w, int u, int t, Node* p) {
        if (u == w.size()) {
            if (t == 0 && p->is_end) return true;
            return false;
        }
        if (t < 0) return false;
        int idx = w[u] - 'a';
        for (int i = 0; i < 26; i ++ ) {
            if (p->son[i]) {
                if (dfs(w, u + 1, t - (i != idx), p->son[i]))
                    return true;
            }
        }
        return false;
    }
};

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary* obj = new MagicDictionary();
 * obj->buildDict(dictionary);
 * bool param_2 = obj->search(searchWord);
 */

class Solution {
public:
    vector<int> p;
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        for (int i = 0; i < 2 * n; i ++ ) p.push_back(i);
        for (auto e : edges) {
            int a = e[0], b = e[1];
            int pa = find(a), pb = find(b);
            if (pa == pb) return {a, b};
            else p[pa] = pb;
        }
        return edges[n - 1];
    }
};

class Solution {
public:
    vector<int> p;
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    bool check(string& a, string& b) {
        if (a == b) return true;
        vector<int> q;
        for (int k = 0; k < a.size(); k ++ ) {
            if (a[k] != b[k]) {
                q.push_back(k);
            }
        }
        if (q.size() != 2) return false;
        int x = q[0], y = q[1];
        return a[x] == b[y] && a[y] == b[x];
    }
    int numSimilarGroups(vector<string>& strs) {
        int n = strs.size();
        for (int i = 0; i < n; i ++ ) {
            p.push_back(i);
        }
        for (int i = 0; i < n; i ++ )
            for (int j = i + 1; j < n; j ++ ) {
                string a = strs[i], b = strs[j];
                if (check(a, b)) {
                    p[find(i)] = find(j);
                }
            }
        int ans = 0;
        for (int i = 0; i < n; i ++ )
            if (find(i) == i)
                ans ++;
        return ans;
    }
};

const int N = 210;
int p[N];
class Solution {
public:
    int n;
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        n = isConnected.size();
        for (int i = 1; i <= n; i ++ ) {
            p[i] = i;
        }
        for (int i = 1; i <= n; i ++ )
            for (int j = i + 1; j <= n; j ++ ) {
                int a = i, b = j;
                if (isConnected[i - 1][j - 1] == 1) {
                    a = find(a), b = find(b);
                    if (a != b) {
                        p[a] = b;
                    }
                }
            }
        int ans = 0;
        for (int i = 1; i <= n; i ++ )
            if (find(i) == i) ans ++;
        return ans;
    }
};

const int N = 2010;
class Solution {
public:
    vector<int> g[N];
    int d[N];
    vector<int> findOrder(int n, vector<vector<int>>& prerequisites) {
        memset(d, 0, sizeof d);
        for (auto p : prerequisites) {
            int a = p[0], b = p[1];
            g[b].push_back(a);
            d[a] ++;
        }
        queue<int> q;
        for (int i = 0; i < n; i ++ )
            if (!d[i])
                q.push(i);

        vector<int> res;
        while (q.size()) {
            auto t = q.front();
            q.pop();
            res.push_back(t);
            for (auto v : g[t]) {
                if (--d[v] == 0)
                    q.push(v);
            }
        }
        if (res.size() != n) return {};
        return res;
    }
};

const int N = 210;
class Solution {
public:
    int f[N][N];
    int ans = 1, n, m;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    vector<vector<int>> g;
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        memset(f, -1, sizeof f);
        g = matrix;
        n = matrix.size(), m = matrix[0].size();
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                ans = max(ans, dfs(i, j));
        return ans;
    }
    int dfs(int x, int y) {
        int& v = f[x][y];
        if (v != -1) return v;
        int res = 1;
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] < g[x][y])
                res = max(res, dfs(a, b) + 1);
        }
        return v = res;
    }
};

class Solution {
public:
    int n = 0;
    double temp;
    double g[30][30];
    bool vis[30];
    unordered_map<string, int> hash;
    int getID(string a) {
        if (!hash.count(a)) hash[a] = n ++;
        return hash[a];
    }
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        for (int i = 0; i < equations.size(); i ++ ) {
            int a = getID(equations[i][0]), b = getID(equations[i][1]);
            g[a][b] = values[i], g[b][a] = 1 / values[i];
        }
        vector<double> res;
        for (auto& t : queries) {
            string a = t[0], b = t[1];
            if (!hash.count(a) || !hash.count(b)) res.push_back(-1);
            else {
                memset(vis, 0, sizeof vis);
                if (dfs(getID(a), getID(b), 1)) res.push_back(temp);
                else res.push_back(-1);
            }
        }
        return res;
    }
    bool dfs(int u, int b, double m) {
        if (u == b) {
            temp = m;
            return true;
        }
        vis[u] = true;
        for (int i = 0; i < n; i ++ ) {
            if (g[u][i] != 0 && !vis[i])
                if (dfs(i, b, m * g[u][i]))
                    return true;
        }
        return false;
    }
};

class Solution {
public:
    int n;
    vector<vector<int>> res, g;
    vector<int> path;
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        g = graph;
        n = g.size();
        dfs(0);
        return res;
    }
    void dfs(int u) {
        path.push_back(u);
        if (u == n - 1) res.push_back(path);
        for (auto& v : g[u]) dfs(v);
        path.pop_back();
    }
};

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        queue<string> q;
        unordered_map<string, int> dist;
        q.push("0000");
        dist["0000"] = 0;
        unordered_set<string> S;
        for (auto& d : deadends) S.insert(d);
        if (S.count("0000")) return -1;
        while (q.size()) {
            auto t = q.front();
            q.pop();
            if (t == target) return dist[t];
            for (int i = 0; i < 4; i ++ ) {
                string s = t;
                int x = s[i] - '0';
                int a[2] = {1, 9};
                for (int j = 0; j < 2; j ++ ) {
                    s[i] = (x + a[j]) % 10 + '0';
                    if (!S.count(s) && !dist.count(s)) {
                        dist[s] = dist[t] + 1;
                        if (s == target) return dist[s];
                        q.push(s);
                    }
                }
            }
        }
        return -1;
    }
};