Untitled

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 2e5 + 10;
vector graph[maxn], rev_graph[maxn];
stack st;
bool visited[maxn];
vector cycle;
void topological_sort(int node) {
    visited[node] = true;
    for(int i = 0; i < (int) graph[node].size(); i++) {
        int neighbour = graph[node][i];
        if(!visited[neighbour]) {
            topological_sort(neighbour);
        }
    }
    st.push(node);
}
void dfs(int node) {
    visited[node] = true;
    cycle.push_back(node);
    for(int i = 0; i < (int) rev_graph[node].size(); i++) {
        int neighbour = rev_graph[node][i];
        if(!visited[neighbour]) {
            dfs(neighbour);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    int t;
    cin >> t;
    
    while(t--) {
        int n;
        cin >> n;
        vector > edges;
        for(int i = 0; i < n; i++) {
            int node;
            cin >> node;
            node--;
            graph[i].push_back(node);
            rev_graph[node].push_back(i);
            edges.push_back({i, node});
        }
        memset(visited, false, sizeof visited);
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                topological_sort(i);
            }
        }
        memset(visited, false, sizeof visited);
        string result = "A";
        int cycles_with_length_of_2 = 0;
        vector cycles_nodes;
        while(!st.empty()) {
            int node = st.top();
            st.pop();
            if(!visited[node]) {
                cycle.clear();
                dfs(node);
                if(cycle.size() > 2) {
                    result = "B";
                    break;
                }
                if(cycle.size() == 2) {
                    cycles_with_length_of_2++;
                    cycles_nodes = cycle;
                }
            }
        }
        
        for(int i = 0; i < n; i++) {
            graph[i].clear();
            rev_graph[i].clear();
        }
        while(!st.empty()) {
            st.pop();
        }
        if(cycles_with_length_of_2 > 1) {
            result = "A";
        }
        else if(cycles_with_length_of_2 == 1){
            result = "BOTH";
//            cout << cycles_nodes[0] << " " << cycles_nodes[1] << endl;
            for(int i = 0; i < n; i++) {
                if(cycles_nodes[0] == edges[i].first and cycles_nodes[1] == edges[i].second) continue;
                if(cycles_nodes[1] == edges[i].first and cycles_nodes[0] == edges[i].second) continue;
                
                if(edges[i].second == cycles_nodes[0] or edges[i].second == cycles_nodes[1]) {
                    result = "BOTH";
                }
                else {
                    result = "A";
                    break;
                }
            }
        }
        cout << result << "\n";
    }
    return 0;
}