class Solution {
    unordered_map<int, unordered_set<int>> adj;
    unordered_set<int> vis;
public:
    bool hasCycle(string graph) {
        adj.clear();
        vis.clear();
        auto& g = graph;
        regex com_reg(",");
        regex arrow_reg("->");
        vector<string> vs(sregex_token_iterator(g.begin(), g.end(), com_reg, -1), sregex_token_iterator());
        for (auto str : vs) {
            vector<string> ve(sregex_token_iterator(str.begin(), str.end(), arrow_reg, -1), sregex_token_iterator());
            adj[atoi(ve[0].c_str())].insert(atoi(ve[1].c_str()));
        }
        for (auto& x : adj)
            if (dfs(x.first))
                return true;
        return false;
    }
    
    bool dfs(int u) {
        vis.insert(u);
        for (int v : adj[u]) {
            if (vis.count(v))
                return true;
            if (dfs(v))
                return true;
        }
        vis.erase(u);
        return false;
    }
};

class Solution {
public:
    int minRemainingSpace(vector<int>& N, int V) {
        int n = N.size();
        vector<int> dp(V + 1, 0);
        for (int i = 0; i < n; ++i)
            for (int j = V; j >= N[i]; --j)
                dp[j] = max(dp[j], dp[j - N[i]] + N[i]);
        return V - dp[V];
    }
};

class Solution {
public:
    int findMaxCI(vector<int>& nums) {
        nums.push_back(-1);
        int n = nums.size();
        int ans = 0, cnt = 1;
        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1])
                ++cnt;
            else {
                ans = max(ans, cnt);
                cnt = 1;
            }
        }
        return ans;
    }
};

const double eps = 1e-8;

struct point {
    double x, y;
    
    point(double _x = 0.0, double _y = 0.0) : x(_x), y(_y) {}
    
    point operator - (const point& p) {
        return point(x - p.x, y - p.y);
    }
    
    double sqrx() {
        return sqrt(x * x + y * y);
    }
};

int dcmp(double x) {
    if (abs(x) < eps)
        return 0;
    return x > 0 ? 1 : -1;
}

double xmult(point& p1, point& p2, point& p0) {
    point pa = p1 - p0;
    point pb = p2 - p0;
    return pa.x * pb.y - pa.y * pb.x;
}

double dmult(point& p1, point& p2, point& p0) {
    point pa = p1 - p0;
    point pb = p2 - p0;
    return pa.x * pb.x + pa.y * pb.y;
}

bool point_on_segment(point& p1, point& p2, point& p0) {
    return dcmp(xmult(p1, p2, p0)) == 0 && dcmp(dmult(p1, p2, p0)) <= 0;
}

int point_in_polygon(point& cp, vector<point>& vp) {
    int n = vp.size() - 1, wn = 0;
    for (int i = 0; i < n; ++i) {
        if (point_on_segment(vp[i], vp[i + 1], cp))
            return 2;
        int f = dcmp(xmult(vp[i], vp[i + 1], cp));
        int fd1 = dcmp(vp[i].y - cp.y);
        int fd2 = dcmp(vp[i + 1].y - cp.y);
        if (f > 0 && fd1 <= 0 && fd2 > 0)
            ++wn;
        else if (f < 0 && fd2 <= 0 && fd1 > 0)
            --wn;
    }
    return wn ? 1 : 0;
}

class Solution {
public:
    bool isPointInPolygon(double x, double y, vector<double>& coords) {
        int n = coords.size();
        vector<point> vp;
        for (int i = 0; i < n; i += 2)
            vp.push_back(point(coords[i], coords[i + 1]));
        point cp(x, y);
        return point_in_polygon(cp, vp) == 1;
    }
};

class Solution {
    vector<int> p;
public:
    bool isCompliance(vector<vector<int>>& distance, int n) {
        auto& d = distance;
        int m = d.size();
        p = vector<int>(m);
        for (int i = 0; i < m; ++i)
            p[i] = i;
        for (int i = 0; i < m; ++i)
            for (int j = i + 1; j < m; ++j)
                if (d[i][j] <= 2) {
                    int fi = findp(i);
                    int fj = findp(j);
                    if (fi != fj)
                        p[fi] = fj;
                }
        unordered_set<int> ust;
        for (int i = 0; i < m; ++i)
            ust.insert(findp(i));
        return ust.size() <= n;
    }
    
    int findp(int x) {
        return p[x] == x ? x : p[x] = findp(p[x]);
    }
};