Tác giả: skyvn97

https://www.youtube.com/live/fL4OzpDDCG8?si=rrpj2HSpsNp8OfGk

#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define fi   first
#define se   second
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define __builtin_popcount __builtin_popcountll
using namespace std;
template<class X,class Y>
    void minimize(X &x,const Y &y) {
        if (x>y) x=y;
    }
template<class X,class Y>
    void maximize(X &x,const Y &y) {
        if (x<y) x=y;
    }
template<class T>
    T Abs(const T &x) {
        return (x<0?-x:x);
    }

/* Author: Van Hanh Pham */

/** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/

class DisjointSet {
private:
    vector<int> lab;

public:
    DisjointSet(int n = 0) {
        if (n > 0) lab.assign(n + 7, -1);
    }

    int find(int x) {
        return lab[x] < 0 ? x : lab[x] = find(lab[x]);
    }

    bool join(int a, int b) {
        int x = find(a);
        int y = find(b);
        if (x == y) return false;
        if (lab[x] > lab[y]) swap(x, y);
        lab[x] += lab[y];
        lab[y] = x;
        return true;
    }
};

const int INF_ANSWER = -1;
void infAnswer(void) {
    printf("%d\n", INF_ANSWER);
    throw INF_ANSWER;
}

#define MAX_NODE   200200
#define MAX_EDGE   200200
const int INF = (int)1e9 + 7;

//Overall
int numNode, numBiEdge, numUniEdge, numBiComp;
pair<int, int> uniEdges[MAX_EDGE];
vector<int> inEdgeNode[MAX_NODE];
vector<int> biAdj[MAX_NODE];
int biCompID[MAX_NODE];

//For components
vector<int> inEdges[MAX_NODE], outEdges[MAX_NODE];
int status[MAX_NODE], maxDistTo[MAX_EDGE];

//For tree
int par[MAX_NODE], high[MAX_NODE];
int maxFarIn[MAX_NODE], maxFarOut[MAX_NODE], maxFar[MAX_NODE];

void resetData(void) {
    REP(i, numNode + 1) inEdgeNode[i].clear();
    REP(i, numNode + 1) biAdj[i].clear();
    memset(biCompID, 0, (numNode + 1) * sizeof (int));

    REP(i, numNode + 1) inEdges[i].clear();
    REP(i, numNode + 1) outEdges[i].clear();
    memset(status, 0, (numNode + 1) * sizeof (int));
    memset(maxDistTo, 0, (numUniEdge + 1) * sizeof (int));

    memset(par, 0, (numNode + 1) * sizeof (int));
    memset(high, 0, (numNode + 1) * sizeof (int));
    memset(maxFarIn, 0, (numNode + 1) * sizeof (int));
    memset(maxFarOut, 0, (numNode + 1) * sizeof (int));
    memset(maxFar, 0, (numNode + 1) * sizeof (int));

    numNode = numBiEdge = numUniEdge = numBiComp = 0;
}

void loadGraph(void) {
    scanf("%d%d%d", &numNode, &numBiEdge, &numUniEdge);
    FOR(i, 1, numBiEdge + numUniEdge) {
        int u, v; scanf("%d%d", &u, &v);
        if (i > numBiEdge) {
            inEdgeNode[v].push_back(i - numBiEdge - 1);
            uniEdges[i - numBiEdge - 1] = make_pair(u, v);
        } else {
            biAdj[u].push_back(v);
            biAdj[v].push_back(u);
        }
    }
}

void checkBiGraph(void) {
    DisjointSet dsu(numNode);
    FOR(i, 1, numNode) FORE(it, biAdj[i]) if (i < *it && !dsu.join(i, *it)) infAnswer();
    FOR(i, 1, numNode) if (dsu.find(i) == i) biCompID[i] = ++numBiComp;
    FOR(i, 1, numNode) if (dsu.find(i) != i) biCompID[i] = biCompID[dsu.find(i)];
}

#define UNVISITED   0
#define VISITING   1
#define VISITED   2

void dfsBiComp(int u) {
    if (status[u] == VISITING) infAnswer();
    status[u] = VISITING;
    FORE(it, outEdges[u]) {
        assert(u == biCompID[uniEdges[*it].fi]);
        int v = biCompID[uniEdges[*it].se];
        if (status[v] != VISITED) dfsBiComp(v);
    }
    status[u] = VISITED;
}

void checkUniGraph(void) {
    REP(i, numUniEdge) {
        int u = uniEdges[i].fi;
        int v = uniEdges[i].se;

        if (biCompID[u] == biCompID[v]) infAnswer();
        inEdges[biCompID[v]].push_back(i);
        outEdges[biCompID[u]].push_back(i);
    }

    FOR(i, 1, numBiComp) if (status[i] == UNVISITED) dfsBiComp(i);
}

void dfsTree(int u) {
    FORE(it, biAdj[u]) if (*it != par[u]) {
        int v = *it;
        par[v] = u;
        //high[v] = high[u] + 1;
        dfsTree(v);
        maximize(maxFarIn[u], maxFarIn[v] + 1);
    }
}

void update(pair<int, int> &a, pair<int, int> &b, const pair<int, int> &c) {
    if (c > a) {
        b = a;
        a = c;
    } else maximize(b, c);
}

int getMaxDistTo(int);

void calcFarOut(int u) {
    maxFar[u] = max(maxFarIn[u], maxFarOut[u]);

    pair<int, int> best[2];
    REP(i, 2) best[i] = make_pair(-INF, -INF);

    FORE(it, inEdgeNode[u]) update(best[0], best[1], make_pair(getMaxDistTo(*it), -1));

    FORE(it, biAdj[u]) if (*it != par[u]) update(best[0], best[1], make_pair(maxFarIn[*it], *it));

    FORE(it, biAdj[u]) if (*it != par[u]) {
        int v = *it;
        maxFarOut[v] = max(maxFarOut[u] + 1, 1);
        maximize(maxFarOut[v], v == best[0].se ? best[1].fi + 2 : best[0].fi + 2);
        calcFarOut(v);
    }
}

void calcMaxFar(int comp, int root) {
    FORE(it, inEdges[comp]) {
        int v = uniEdges[*it].se;
        assert(biCompID[v] == comp);
        maximize(maxFarIn[v], getMaxDistTo(*it) + 1);
    }

    dfsTree(root);
    maxFarOut[root] = -INF;
    calcFarOut(root);
}

int getMaxFar(int u) {
    if (maxFar[u] < 0) calcMaxFar(biCompID[u], u);
    return maxFar[u];
}

int getMaxDistTo(int edgeID) {
    if (maxDistTo[edgeID] >= 0) return maxDistTo[edgeID];
    int node = uniEdges[edgeID].fi;
    return maxDistTo[edgeID] = getMaxFar(node);
}

void process(void) {
    memset(maxFar, -1, sizeof maxFar);
    memset(maxDistTo, -1, sizeof maxDistTo);

    int res = 0;
    FOR(i, 1, numNode) maximize(res, getMaxFar(i));
    printf("%d\n", res);
}

int main(void) {
#ifdef ONLINE_JUDGE
    freopen("fakerfmvp.inp", "r", stdin);
    freopen("fakerfmvp.out", "w", stdout);
#endif // ONLINE_JUDGE

    int numTest; scanf("%d", &numTest);
    REP(faker, numTest) {
        try {
            loadGraph();
            checkBiGraph();
            checkUniGraph();
            process();
        } catch (int x) {
            assert(x == INF_ANSWER);
        }
        resetData();
    }
    return 0;
}

/*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/