Untitled

#include <chrono>
#include <iostream>

using namespace std;
using namespace std::chrono;

#define opt __attribute((optimize("Ofast")))

#define MAX_STUDENT 100001
#define NO_COLOR 0
#define BLUE 1
#define PINK 2

int T, tc, n, m, f1, f2;
char gender;
bool isBoy[MAX_STUDENT];
int color[MAX_STUDENT];
int inversion;
int wear;
int line = 0;

template <typename TYPE>
class Vector {
public:
    TYPE* data;
    int size;
    int capacity;
    Vector() {
        size = 0;
        capacity = 10;
        data = new TYPE[10];
    }
    void reset() {
        size = 0;
        capacity = 10;
        delete[] data;
        data = new TYPE[10];
    }
    void push(TYPE value) {
        if (size == capacity) {
            capacity *= 10;
            TYPE* temp = new TYPE[capacity];
            for (int i = 0; i < size; i++) {
                temp[i] = data[i];
            }
            delete[] data;
            data = temp;
        }
        data[size++] = value;
    }
};

class Node {
public:
    Vector <int> relation;
    int getRelation(int i) { return relation.data[i]; }
} nodes[MAX_STUDENT];

void backtrack(int current, int previousColor) {
    if (wear >= n)
        return;
    if (color[current] == previousColor) {
        inversion = -1;
        wear = n + 1;
        return;
    }
    else if (color[current] != NO_COLOR)
        return;
    color[current] = (previousColor == PINK) ? BLUE : PINK;
    wear++;
    if ((isBoy[current] && color[current] == PINK) || (!isBoy[current] && color[current] == BLUE))
        inversion++;
    for (int i = 0; i < nodes[current].relation.size; i++) {
        backtrack(nodes[current].getRelation(i), color[current]);
    }
}

opt int main(int argc, char** argv) { //84ms
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("input.txt", "r", stdin);
    auto st = high_resolution_clock::now();
    cin >> T;
    line++;
    for (tc = 1; tc <= T; ++tc) {
        inversion = 0;
        wear = 0;
        cin >> n >> m; line++;
        //cout << "Size: " << line << " " << n << endl;
        line++;
        for (int i = 1; i <= n; i++) {
            cin >> gender;
            if (gender == 'B')
                isBoy[i] = true;
            else
                isBoy[i] = false;
            nodes[i].relation.reset();
            color[i] = NO_COLOR;
            //cout << i << endl;
        }
        // Relationship
        for (int i = 0; i < m; i++) {
            cin >> f1 >> f2; line++;
            nodes[f1].relation.push(f2);
            nodes[f2].relation.push(f1);
        }
        backtrack(1, BLUE);
        if (inversion > (n / 2))
            inversion = n - inversion;
        if (wear < n) {
            inversion = -1;
        }
        cout << "#" << tc << " " << inversion << endl;
    }
    auto en = high_resolution_clock::now();
    double T = duration_cast<nanoseconds>(en - st).count();
    cout << T / 1e9 << endl;
    return 0;
}