算法

(抽屉原理) $O(T^2)$

本题比较 $ad-hoc$ （可以理解为奇技淫巧）
由于 $V_1$ 和 $V_2$ 都是独立集，所以 $4$ 环 中有两点出自 $V_1$，另外两点出自 $V_2$
假设 $4$ 环中位于 $V_1$ 的两点为 $x, y$，位于 $V_2$ 的两点为 $a,b$
枚举点 $x$，可以找到 $T(T-1)$ 对使得 $a \neq b$ 且 $(x, a)$ 与 $(x, b)$ 都有连边的二元组 $(a, b)$。
注意到 $T$ 的上界为 $3000$，所以至多有 $9 \times 10^6$ 对不同的二元组 $(a, b)$。由抽屉原理可知，若枚举 $T(T-1)+1$ 次，一定会遇到重复的二元组 $(a, b)$。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using ll = long long;

int main() {
    int s, t, m;
    cin >> s >> t >> m;

    vector<vector<int>> to(s);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        b -= s;
        to[a].push_back(b);
    }

    vector id(t, vector<int>(t, -1));
    rep(v, s) {
        int d = to[v].size();
        sort(to[v].begin(), to[v].end());
        rep(i, d)rep(j, i) {
            int a = to[v][j], b = to[v][i];
            if (id[a][b] == -1) {
                id[a][b] = v;
            }
            else {
                int u = id[a][b];
                a += s+1;
                b += s+1;
                v++; u++;
                cout << a << ' ' << b << ' ' << v << ' ' << u << '\n';
                return 0;
            } 
        }
    }

    puts("-1");

    return 0;
}