首先是二分答案，找到一个最小的值mid使得所有罪犯的冲突最大是mid。

然后是check。
对于一条边k，很容易想到如果k > mid那么两个顶点不在一个监狱，否在能在一个监狱。

这里的不在和在两种关系看起来都有传递性，但是在这种关系是不确定的，也就是说两个顶点如果边权小于mid那么他们可以在一个监狱也可以不在一个监狱。所以并不具有传递性。

于是选择不在作为关系进行传递。若冲突大于mid则把两个顶点建立关系。

设1代表a b不能在一个监狱。

在此之前先检测两个点是否在一个并查集里面.

如果在，检查并查集的边权之和是否是2的倍数。如果是则冲突。因为a^c^b如果是0的话代表a b在一个监狱。也就是说b不在a不在那个监狱，那么b就在a所在的监狱。

我的代码里用了异或运算来实现对2取模，因为异或就是不进位加法，相当于自动取模

否则关系成立。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
struct rec{
    int x, y, k;
    bool operator<(const rec & b)
    {
        return k < b.k;
    }
}q[maxn];
int fa[maxn], d[maxn];
int ff(int x)
{
    if(fa[x] == x) return x;
    int r = ff(fa[x]);
    d[x] ^= d[fa[x]];
    return fa[x] = r;
}
int main()
{
    int n, m; cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int a,b,k;
        scanf("%d%d%d", &a, &b, &k);
        q[i] = {a, b, k};
    }
    //sort(q + 1, q + 1 + m);
    int l = 0, r = 1000000000;
    //int l = 0, r = 30000;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        int flag = 1;
        for(int i = 1; i <= n; i++) fa[i] = i;
        memset(d, 0, sizeof d);
        for(int i = 1; i <= m; i++)
        {
            if(q[i].k > mid)
            {
                int x = ff(q[i].x), y = ff(q[i].y);
                if(x == y)
                {
                    if(d[q[i].x] ^ d[q[i].y] != 1)
                    {
                        flag = 0;
                        break;
                    }
                }
                else
                {
                    fa[x] = y;
                    d[x] = d[q[i].x] ^  d[q[i].y] ^ 1;
                }
            }
        }
        if(flag) r = mid;
        else l = mid + 1;
    }
    cout << l;
}