Untitled

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Comparator function to sort intervals based on the start time
bool compare_intervals(const pair<int, int>& a, const pair<int, int>& b) {
    return a.first < b.first;
}

vector<pair<int, int>> find_available_slots(vector<pair<int, int>>& practice_slots) {
    if (practice_slots.empty()) {
        // If there are no existing practice slots, the entire day is available
        return {{0, 1000000000}};
    }

    // Sort the practice slots based on the start time
    sort(practice_slots.begin(), practice_slots.end(), compare_intervals);

    // Merge overlapping intervals
    vector<pair<int, int>> merged_slots;
    merged_slots.push_back(practice_slots[0]);

    for (size_t i = 1; i < practice_slots.size(); ++i) {
        if (practice_slots[i].first <= merged_slots.back().second) {
            // There is an overlap, merge the intervals
            merged_slots.back().second = max(merged_slots.back().second, practice_slots[i].second);
        } else {
            // No overlap, add the current interval to merged_slots
            merged_slots.push_back(practice_slots[i]);
        }
    }

    // Find available time frames between merged slots
    vector<pair<int, int>> available_slots;
    if (merged_slots[0].first > 0) {
        // If there is a gap before the first practice slot
        available_slots.push_back({0, merged_slots[0].first});
    }

    for (size_t i = 1; i < merged_slots.size(); ++i) {
        if (merged_slots[i].first > merged_slots[i - 1].second) {
            // If there is a gap between two merged slots
            available_slots.push_back({merged_slots[i - 1].second, merged_slots[i].first});
        }
    }

    if (merged_slots.back().second < 1000000000) {
        // If there is a gap after the last practice slot
        available_slots.push_back({merged_slots.back().second, 1000000000});
    }

    if (available_slots.empty()) {
        // If no available slots found, return [-1, -1]
        return {{-1, -1}};
    }

    return available_slots;
}

int main() {
    int t;
    cin >> t;
    for(int val = 0; val < t; val++) {
        int n; 
        cin >> n;
        vector<pair<int,int>>practice_slots(n);
        for(int i = 0; i < n; i++) {
            cin >> practice_slots[i].first;
        }
        for(int i = 0; i < n; i++) {
            cin >> practice_slots[i].second;
        }
        vector<pair<int, int>> available_slots = find_available_slots(practice_slots);
    
        for (const auto& slot : available_slots) {
            cout << slot.first << " " << slot.second << "\n";
        }
    }
    return 0;
}