#include<bits/stdc++.h>

#ifdef std1
using namespace std;
#endif
#ifdef xy
#define x first
#define y second
#endif
int n, m;
const int N = 50010;
int p[N], d[N];
int find(int x) {
    if (p[x] != x) {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}
signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    std::iota(p, p + N, 0);
    std::cin>>n>>m;
    int res = 0;
    while (m--){
        int t, x, y;
        std::cin >> t >> x >> y;
        if (x > n || y > n) res++;
        else{
            int px = find(x), py = find(y);
            if (t == 1){
                if (px == py && (d[x] - d[y]) % 3) res++;
                else if (px != py){
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else{
                if (px == py && (d[x] - d[y] - 1) % 3) res++;
                else if (px != py){
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    std::cout << res << '\n';
    return 0;
}

#include<bits/stdc++.h>
#ifdef std1
using namespace std;
#endif
#ifdef xy
#define x first
#define y second
#endif
const int N = 1e6 + 10;
int fa[N], dis[N], size[N];
signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int k, x, y; std::cin >> k;
    std::fill(size, size + N, 1); std::iota(fa, fa + N, 0);
    std::function<int(int)> find = [&](int x) {
        if (x != fa[x]) {
            int f = find(fa[x]); dis[x] += dis[fa[x]];
            fa[x] = f;
        }
        return fa[x];
    };
    auto merge = [&](int x, int y) {
        int fx = find(x), fy = find(y);
        fa[fx] = fy; dis[fx] += size[fy]; size[fy] += size[fx];
    };
    for (int i = 0; i < k; i++) {
        char op; std::cin >> op;
        if (op == 'M') { std::cin >> x >> y; merge(x, y); continue; }
        std::cin >> x; find(x);
        std::cout << dis[x] << '\n';
    }
    return 0;
}

#define x first
#define y second
using i64 = long long;
class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        int n = nums.size();
        std::unordered_map<int, int> a;
        std::vector<int> res;
        for (int i = 0; i < n; i++) {
            auto it = a.find(target - nums[i]);
            if (it != a.end()) return { it->y,i };
            a[nums[i]] = i;
        }
        return {};
    }
};

#pragma GCC otimize("O3")
#define LOCAL
int S[1010];
using i64 = long long;
int init = []() {
    for (int i = 1; i <= 1000; i++) {
        auto s = std::to_string(i * i);
        int n = s.size();
        std::function<bool(int, int)> dfs = [&](int p, int sum)->bool {
            if (p == n) return sum == i;
            int x = 0;
            for (int j = p; j < n; j++) {
                x = x * 10 + int(s[j] - '0');
                if (dfs(j + 1, sum + x)) return true;
            }
            return false;
        };
        S[i] = S[i - 1] + (dfs(0, 0) ? i * i : 0);
    }
    return 0;
}();
class Solution {
    using i64 = long long;
public:
    int punishmentNumber(int n) {
        return S[n];
    }
};
#ifdef LOCAL
#define x first
#define y second
#elif LOCAL2
using namespace std;
using PII = pair<int, int>;
#endif

class Solution {
public:
    std::string makeSmallestPalindrome(std::string s) {
        int n = s.size();
        int mid = n - 1 >> 1;
        for (int l = mid, r = n>>1; l >= 0 && r < n; l--, r++) {
            if (s[l] != s[r]) {
                if (s[l] < s[r]) s[r] = s[l];
                else s[l] = s[r];
            }
        }
        return s;
    }
};

class Solution {
public:
    int minLength(string s) {
        while (s.find("AB") != -1 || s.find("CD") != -1) {
            auto it1 = s.find("AB");
            if (it1 != -1) s.erase(it1,2);
            auto it2 = s.find("CD");
            if (it2 != -1) s.erase(it2,2);
        }
        return s.size();
    }
};

#include<bits/stdc++.h>
const int N = 1e6 + 10;
int a[N];
signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n; std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    std::priority_queue<int, std::vector<int>, std::greater<int>> q;
    int64_t res = 0;
    for (int i = 1; i <= n; i++) {
        if (q.size() && a[i] > q.top()) {
            res += a[i] - q.top(); q.pop();
            q.push(a[i]); q.push(a[i]);
        }
        else q.push(a[i]);
    }
    std::cout << res << '\n';
    return 0;
}

#include<bits/stdc++.h>
signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n; std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::string s,res; std::cin >> s;
        int cnta = std::count(s.begin(), s.end(), 'A'), cntb = std::count(s.begin(), s.end(), 'B');
        int cntn = std::count(s.begin(), s.end(), 'N');
        while (cnta || cntb || cntn) {
            if (cntn) res += 'N', cntn--;if (cntb) res += 'B', cntb--;
            if (cnta) res += 'A', cnta--;
        }
        std::cout << "case #" << i << ":\n" << res<<'\n';
        res.clear(), s.clear();
    }
    return 0;
}

现接收到一大批电子邮件，邮件地址格式为：用户名@主机域名，要求把这些电子邮件地址做主机域名的字典序升序排序，如果主机域名相同，则做用户名的字典序降序排序。

#include<bits/stdc++.h>
// 重新定义std::string的小于号运算符
bool operator<(const std::string& a, const std::string& b) {
    return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
}

// 在solve类中实现小于号运算符
class solve {
public:
    std::string a, b;
    bool operator<(const solve& S) const {
        if (b != S.b) {
            return b < S.b;
        }
        return a > S.a;
    }
};
signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n; std::cin >> n;
    std::vector<solve> v(n);
    for (int i = 0; i < n; i++) {
        std::string email;
        std::cin >> email;
        int pos = email.find('@');
        v[i].a = email.substr(0, pos);
        v[i].b = email.substr(pos + 1);
    }
    std::sort(v.begin(), v.end());

    for (int i = 0; i < n; i++) {
        std::cout << v[i].a << '@' << v[i].b << '\n';
    }
}

#pragma GCC otimize("O2")
#pragma GCC otimize("O3")
#pragma GCC otimize("O2")
#include<bits/stdc++.h>

using namespace std;

inline int qr() {
    int f = 0, fu = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')fu = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        f = (f << 3) + (f << 1) + c - 48;
        c = getchar();
    }
    return f * fu;
}

const int N = 1e3 + 10, M = 1e5 + 10;

struct Leftist_Tree {
    int tot, rt[N];
    struct node {
        int dis, lc, rc, x, val;
    } t[N * 45];

    Leftist_Tree() { t[0].dis = -1; }

    inline int merge(int x, int y) {
        if (!x || !y)return x | y;
        if (t[x].val > t[y].val)swap(x, y);
        int p = ++tot;
        t[p] = t[x], t[p].rc = merge(t[x].rc, y);
        if (t[t[p].lc].dis < t[t[p].rc].dis)swap(t[p].lc, t[p].rc);
        t[p].dis = t[t[p].rc].dis + 1;
        return p;
    }

    inline void insert(int &p, int x, int v) {
        ++tot, t[tot] = {0, 0, 0, x, v};
        p = merge(p, tot);
    }
} L;

struct Kth_Path {
    int n, m, S, T, K;
    int head[N], ver[M], edge[M], Next[M], tot;
    int rh[N], rv[M], re[M], rn[M], rt;
    int d[N], fa[N];
    bool v[N], vis[N], ot[M];

    inline void add(int x, int y, int z) {
        ver[++tot] = y;
        edge[tot] = z;
        Next[tot] = head[x];
        head[x] = tot;
    }

    inline void add_r(int x, int y, int z) {
        rv[++rt] = y;
        re[rt] = z;
        rn[rt] = rh[x];
        rh[x] = rt;
    }

    struct node {
        int x, v;

        inline bool operator<(node a) const {
            return v > a.v;
        }
    };

    inline void dijkstra() {
        memset(d, 0x3f, sizeof(int) * (n + 1));
        memset(vis, false, sizeof(bool) * (n + 1));
        priority_queue<node> q;
        d[T] = 0;
        q.push({T, 0});
        while (!q.empty()) {
            int x = q.top().x;
            q.pop();
            if (vis[x])continue;
            vis[x] = true;
            for (int i = rh[x]; i; i = rn[i]) {
                int y = rv[i], z = re[i];
                if (d[y] > d[x] + z)d[y] = d[x] + z, q.push({y, d[y]});
            }
        }
    }

    inline void init() {
        tot = rt = 0;
        memset(head, 0, sizeof(int) * (n + 1));
        memset(rh, 0, sizeof(int) * (n + 1));
    }

    inline void bfs1() {
        queue<int> q;
        memset(ot, false, sizeof(bool) * (m + 1));
        memset(v, false, sizeof(bool) * (n + 1));
        v[T] = true, q.push(T);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (int i = rh[x]; i; i = rn[i]) {
                int y = rv[i], z = re[i];
                if (v[y] || d[y] != d[x] + z)continue;
                fa[y] = x, v[y] = ot[i] = true, q.push(y);
            }
        }
    }

    inline void bfs2() {
        queue<int> q;
        memset(v, false, sizeof(bool) * (n + 1));
        v[T] = true, q.push(T);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            if (fa[x])L.rt[x] = L.merge(L.rt[x], L.rt[fa[x]]);
            for (int i = rh[x]; i; i = rn[i])
                if (ot[i] && !v[rv[i]])v[rv[i]] = true, q.push(rv[i]);
        }
    }

    inline int solve() {
        n = qr(), m = qr(), init();
        for (int i = 1; i <= m; i++) {
            int x = qr(), y = qr(), z = qr();
            add(x, y, z), add_r(y, x, z);
        }
        S = qr(), T = qr(), K = qr();
        if (S == T)K++;
        dijkstra();
        if (!vis[S])return -1;
        if (K == 1)return d[S];
        bfs1();
        for (int x = 1; x <= n; x++) {
            if (!vis[x])continue;
            for (int i = head[x]; i; i = Next[i])
                if (!ot[i] && vis[ver[i]])
                    L.insert(L.rt[x], ver[i], d[ver[i]] + edge[i] - d[x]);
        }
        bfs2();
        priority_queue<node> q;
        if (L.rt[S])q.push({L.rt[S], d[S] + L.t[L.rt[S]].val});
        K--;
        while (!q.empty()) {
            node t = q.top();
            q.pop();
            if (!--K)return t.v;
            if (L.t[t.x].lc)q.push({L.t[t.x].lc, t.v - L.t[t.x].val + L.t[L.t[t.x].lc].val});
            if (L.t[t.x].rc)q.push({L.t[t.x].rc, t.v - L.t[t.x].val + L.t[L.t[t.x].rc].val});
            if (L.rt[L.t[t.x].x])q.push({L.rt[L.t[t.x].x], t.v + L.t[L.rt[L.t[t.x].x]].val});
        }
        return -1;
    }
} K;

int main() {
    printf("%d\n", K.solve());
    return 0;
}