HackerRank Recording Episodes Problem Solution

HackerRank Recording Episodes Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Recording Episodes Problem Solution.

Dave is a die-hard fan of a show called “HackerRank”, in which a young programmer uses her problem-solving abilities to solve crimes. He splurged on a Digital Video Recorder (DVR) so that he can record HackerRank episodes and watch them later. Luckily, Dave managed to get his hands on schedules for all the episodes in each upcoming season.
Each season has n episodes numbered from 1 to n. Each episode airs twice; the first time it’s called “live”, and the second time it’s called “repeat”. So, for each episode, we have 4 integers, (Slive and elve) for the live airing and (Srepeat and repeat) for the repeat airing, where s is episode’s start time and and e is its end time. All times are given as integers representing the number of minutes passed since the start of the season. Episodes broadcast on multiple channels, so some of the air times overlap and the episodes may not broadcast sequentially. It’s possible that both the live and repeat broadcasts of some episode i are held before episode j, even though i > j. In addition, live and repeat broadcasts of the same episode may differ in length due to the number of advertisements during the broadcast.
Dave only has one TV with a DVR attached to it, and the DVR is capable of recording one episode at a time. For each episode in a season, Dave first decides whether or not he will record it. If he decides to record it, he will either record it during (Stive, live) or (Srepeat, Crepeat). Dave will only ever record one of the two airings of an episode, and he always records full episodes. This means that once he starts recording an episode, he will always record it until the end (l.e., he never records partial episodes).

Dave realizes that it might not be possible for him to record all episodes successfully, so instead of focusing on recording all episodes of HackerRank (which may be impossible), he decides to record all consecutively airing episodes whose episode number occurs in some inclusive [L, R] interval such that R-L (i.e., the number of consecutive episodes recorded) is as large as possible.
Given the programming schedule for each season, find L and R episode numbers for largest range of consecutive episodes Dave can record during that season and print these respective values as two space-separated integers on a new line. If two or more such intervals exist, choose the one having the smallest I value.
Input Format
The first line contains a single positive integer, q, denoting number of seasons of HackerRank.
The subsequent lines describe each of the q seasons in the following format:

  1. The first line contains an integer, n, denoting the number of episodes in the season.
  2. Each line of the n subsequent line contains four space-separated integers describing the respective values of Stive Clive Srepeat, and erepeat.

Output Format
On a new line for each season, print two space-separated integers denoting the respective L and R (inclusive) values for the maximum possible range of consecutive episodes Dave can record such that R-L is as large as possible. If more than one such interval exists. choose the interval having the smallest L.

Sample Input

3
3
10 20 30 40
20 35 21 35
14 30 35 50
1
10 20 30 40
3
11 19 31 39
12 38 13 37
10 20 30 40

Sample Output

1 2
1 1
1 1

Explanation
For the first season, Dave records the live airing of episode 1 and the repeat airing of episode 2. Note that it is not possible to record episodes 1, 2 and 3 simultaneously. For the second season, there is only one episode so Dave records from episode 1 to episode 1 and we print 1 1 on a new line.
For the third season. Dave must choose to record either episode 1 or episode 3 (episode 2 starts while episode 1 is still airing and ends after episode 3 starts); he cannot record both. because he only wants to record consecutive episodes. Thus, we pick the episode with the smallest Д value, which is episode 1, and print 1 1 as we are only recording episode 1.

HackerRank Recording Episodes Problem Solution
HackerRank Recording Episodes Problem Solution

Recording Episodes C Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct episode {
  int x;
  int w;
  struct episode *next;
} epic;
void spare();
void change(int x, int y, int w);
int around();
void dfs1(int x);
void dfs2(int x);
int checkx(int x);
int l,r,n,st,c,a[4][100],mark[400],component[400],s[400];
epic *table[400] = {0}, *rtable[400] = {0};

int main(){
  int q,max,maxi,i,j;
  scanf("%d",&q);
  while(q--){
    scanf("%d",&n);
    for(i=0;i<n;i++)
      scanf("%d%d%d%d",&a[0][i],&a[1][i],&a[2][i],&a[3][i]);
    for(i=0;i<n;i++){
      change(2 * n + i, n + i, 1);
      change(3 * n + i, i, 1);
      for(j=0;j<n;j++){
        if(i==j)
          continue;
        if(!(a[0][i]>a[1][j] || a[0][j]>a[1][i]))
          change(i, 2 * n + j, 1);
        if(!(a[2][i]>a[1][j] || a[0][j]>a[3][i]))
          change(n + i, 2 * n + j, 1);
        if(!(a[0][i]>a[3][j] || a[2][j]>a[1][i]))
          change(i, 3 * n + j, 1);
        if(!(a[2][i]>a[3][j] || a[2][j]>a[3][i]))
          change(n + i, 3 * n + j, 1);
      }
    }
    max=1;
    maxi=0;
    for(i=0;i<n;i++)
      for(j=max+1;i+j<=n;j++){
        l=i;
        r=i+j-1;
        if (around()) {
          max=j;
          maxi=i;
        } else
          break;
      }
    printf("%d %d\n",maxi+1,maxi+max);
    spare();
  }
  return 0;
}
void spare() {
  int i;
  epic *p, *pp;
  for(i=0;i<400;i++)
    if(table[i]){
      p=table[i];
      while(p){
        pp=p->next;
        free(p);
        p=pp;
      }
      table[i]=NULL;
    }
  for(i=0;i<400;i++)
    if(rtable[i]){
      p=rtable[i];
      while(p){
        pp=p->next;
        free(p);
        p=pp;
      }
      rtable[i]=NULL;
    }
  return;
}
void change(int x, int y, int w) {
  epic *t = malloc(sizeof(epic));
  t->x=y;
  t->w=w;
  t->next=table[x];
  table[x]=t;
  t = malloc(sizeof(epic));
  t->x=x;
  t->w=w;
  t->next=rtable[y];
  rtable[y]=t;
  return;
}
int around() {
  int i;
  st=c=0;
  memset(mark,0,sizeof(mark));
  memset(component,0,sizeof(component));
  for(i=0;i<4*n;i++)
    if(!mark[i] && checkx(i))
      dfs1(i);
  memset(mark,0,sizeof(mark));
  while(st){
    if(!mark[s[st-1]]){
      c++;
      dfs2(s[st-1]);
    }
    st--;
  }
  for(i=0;i<2*n;i++)
    if(component[i]==component[i+2*n] && component[i] && checkx(i) && checkx(i+2*n))
      return 0;
  return 1;
}
void dfs1(int x){
  epic *p;
  mark[x]=1;
  for(p=table[x];p;p=p->next)
    if(!mark[p->x] && checkx(p->x))
      dfs1(p->x);
  s[st++]=x;
  return;
}
void dfs2(int x){
  epic *p;
  mark[x]=1;
  for(p=rtable[x];p;p=p->next)
    if(!mark[p->x] && checkx(p->x))
      dfs2(p->x);
  component[x]=c;
  return;
}
int checkx(int x){
  return (x>=l && x<=r || x>=l+n && x<=r+n || x>=l+2*n && x<=r+2*n || x>=l+3*n && x<=r+3*n);
}

Recording Episodes C++ Solution

#include <bits/stdc++.h>

using namespace std;
int n,q;

vector<int> dfs_num,dfs_low,visited,S;
vector<vector<int>> graph;
vector<int> parent;
int idx = 0,dfs_counter = 0,scc_ind;

int not_ind(int x){
    return 2*n + x;
}

void tarjanSCC(int u){
    dfs_num[u] = dfs_low[u] = dfs_counter++;
    visited[u] = 1;
    S.push_back(u);
    for(auto&v : graph[u]){
        if(dfs_num[v] == -1) tarjanSCC(v);
        if (visited[v]==1) dfs_low[u] = min(dfs_low[u],dfs_low[v]);
    }
    if (dfs_num[u] == dfs_low[u]){
        while(true){
        int v = S.back();S.pop_back();visited[v] = 0;
        parent[v] = scc_ind;
            if (v==u) break;
        }
        scc_ind++;
    }
}

bool sat(){
    for(auto&x : dfs_num) x = -1;
    for(auto&x : visited) x = 0;
    dfs_counter = 0;
    scc_ind = 0;
    idx = 0,dfs_counter = 0;
    S.clear();
    for(int i=0;i<4*n;i++){
        if (dfs_num[i] == -1) tarjanSCC(i);
    }
    for(int i=0;i<2*n;i++){
        if (parent[i]==parent[not_ind(i)]) {
            //cout << i << ' ' << not_ind(i) << ' ' << "f\n";
            return false;
        }
    }
    return true;
}

bool overlap(pair<int,int>& a,pair<int,int>&b){
    if (b < a) return overlap(b,a);
    return b.first <= a.second;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    cin >> q;
    for(int cn=0;cn<q;cn++){
        cin >> n;
        graph.resize(4*n);
        dfs_low.resize(4*n);
        dfs_num.resize(4*n);
        visited.resize(4*n);
        parent.resize(4*n);
        vector<pair<int,int>> vec(2*n);
        for(int i=0;i<2*n;i++){
            cin >> vec[i].first >> vec[i].second;
        }
        int l=0,r=0;
        for(int i=0;i<2*n;i+=2){
            for(auto&x : graph) x.clear();
            for(int j=i;j<2*n;j+=2){
                graph[not_ind(j)].push_back(j+1);
                graph[not_ind(j+1)].push_back(j);
                graph[j].push_back(not_ind(j+1));
                graph[j+1].push_back(not_ind(j));
                for(int k=j-1;k>=i;k--){
                    if (overlap(vec[j],vec[k])){
                        graph[k].push_back(not_ind(j));
                        graph[j].push_back(not_ind(k));
                    }
                    if (overlap(vec[j+1],vec[k])){
                        graph[k].push_back(not_ind(j+1));
                        graph[j+1].push_back(not_ind(k));
                    }
                }
                if ( ((j-i)/2 + 1) > (r-l+1)){
                    if (!sat()) break;
                    if (((j-i)/2 + 1) > (r-l+1)){
                        l = i/2;
                        r = j/2;
                    }
                }
            }
        }
        cout << l+1 << ' ' << r+1 << '\n';
    }
    return 0;
}

Recording Episodes C Sharp Solution

using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading;

public class Solver
{
    static class TwoSat
    {
        static List<int>[] g, gr;
        static bool[] used;
        static List<int> order;
        static int[] comp;

        static void Dfs1(int x)
        {
            if (used[x])
                return;
            used[x] = true;
            foreach (int e in g[x])
                Dfs1(e);
            order.Add(x);
        }

        static void Dfs2(int x, int c)
        {
            if (comp[x] != -1)
                return;
            comp[x] = c;
            foreach (int e in gr[x])
                Dfs2(e, c);
        }

        public static bool[] Match(List<int>[] g)
        {
            TwoSat.g = g;
            int n = g.Length / 2;
            gr = Init<List<int>>(2 * n);
            for (int i = 0; i < 2 * n; i++)
                foreach (int e in g[i])
                    gr[e].Add(i);

            used = new bool[2 * n];
            order = new List<int>();
            for (int i = 0; i < 2 * n; i++)
                Dfs1(i);

            comp = Enumerable.Repeat(-1, 2 * n).ToArray();
            for (int i = 0, j = 0; i < 2 * n; i++)
            {
                int x = order[2 * n - i - 1];
                if (comp[x] == -1)
                    Dfs2(x, j++);
            }

            bool[] ret = new bool[n];
            for (int i = 0; i < n; i++)
                if (comp[i] == comp[i + n])
                    return null;
                else
                    ret[i] = comp[i] > comp[i + n];

            return ret;
        }
    }

    bool Between(int x1, int y1, int x2, int y2)
    {
        return x1 >= x2 && x1 <= y2 || y1 >= x2 && y1 <= y2 || x2 >= x1 && x2 <= y1 || y2 >= x1 && y2 <= y1;
    }

    int[] l1, r1, l2, r2;
    bool Fun(int l, int r)
    {
        int n = r - l + 1;
        var g = Init<List<int>>(2 * n);
        for (int i = l; i <= r; i++)
            for (int j = i + 1; j <= r; j++)
            {
                if (Between(l1[i], r1[i], l1[j], r1[j]))
                {
                    g[i - l].Add(j - l + n);
                    g[j - l].Add(i - l + n);
                }
                if (Between(l1[i], r1[i], l2[j], r2[j]))
                {
                    g[i - l].Add(j - l);
                    g[j - l + n].Add(i - l + n);
                }
                if (Between(l2[i], r2[i], l1[j], r1[j]))
                {
                    g[i - l + n].Add(j - l + n);
                    g[j - l].Add(i - l);
                }
                if (Between(l2[i], r2[i], l2[j], r2[j]))
                {
                    g[i - l + n].Add(j - l);
                    g[j - l + n].Add(i - l);
                }
            }
        return TwoSat.Match(g) != null;
    }

    public void Solve()
    {
        for (int tt = ReadInt(); tt > 0; tt--)
        {
            int n = ReadInt();
            l1 = new int[n];
            l2 = new int[n];
            r1 = new int[n];
            r2 = new int[n];
            for (int i = 0; i < n; i++)
            {
                l1[i] = ReadInt();
                r1[i] = ReadInt();
                l2[i] = ReadInt();
                r2[i] = ReadInt();
            }

            int p = 0;
            int best = 0, ansl = 0, ansr = 0;
            for (int i = 0; i < n; i++)
            {
                while (p < i && !Fun(p, i))
                    p++;
                if (i - p + 1 > best)
                {
                    best = i - p + 1;
                    ansl = p + 1;
                    ansr = i + 1;
                }
            }

            Write(ansl, ansr);
        }
    }

    #region Main

    protected static TextReader reader;
    protected static TextWriter writer;
    static void Main()
    {
#if DEBUG
        reader = new StreamReader("..\\..\\input.txt");
        //reader = new StreamReader(Console.OpenStandardInput());
        writer = Console.Out;
        //writer = new StreamWriter("..\\..\\output.txt");
#else
        reader = new StreamReader(Console.OpenStandardInput());
        writer = new StreamWriter(Console.OpenStandardOutput());
        //reader = new StreamReader("input.txt");
        //writer = new StreamWriter("output.txt");
#endif
        try
        {
            new Solver().Solve();
            //var thread = new Thread(new Solver().Solve, 1024 * 1024 * 128);
            //thread.Start();
            //thread.Join();
        }
        catch (Exception ex)
        {
#if DEBUG
            Console.WriteLine(ex);
#else
            throw;
#endif
        }
        reader.Close();
        writer.Close();
    }

    #endregion

    #region Read / Write
    private static Queue<string> currentLineTokens = new Queue<string>();
    private static string[] ReadAndSplitLine() { return reader.ReadLine().Split(new[] { ' ', '\t', }, StringSplitOptions.RemoveEmptyEntries); }
    public static string ReadToken() { while (currentLineTokens.Count == 0)currentLineTokens = new Queue<string>(ReadAndSplitLine()); return currentLineTokens.Dequeue(); }
    public static int ReadInt() { return int.Parse(ReadToken()); }
    public static long ReadLong() { return long.Parse(ReadToken()); }
    public static double ReadDouble() { return double.Parse(ReadToken(), CultureInfo.InvariantCulture); }
    public static int[] ReadIntArray() { return ReadAndSplitLine().Select(int.Parse).ToArray(); }
    public static long[] ReadLongArray() { return ReadAndSplitLine().Select(long.Parse).ToArray(); }
    public static double[] ReadDoubleArray() { return ReadAndSplitLine().Select(s => double.Parse(s, CultureInfo.InvariantCulture)).ToArray(); }
    public static int[][] ReadIntMatrix(int numberOfRows) { int[][] matrix = new int[numberOfRows][]; for (int i = 0; i < numberOfRows; i++)matrix[i] = ReadIntArray(); return matrix; }
    public static int[][] ReadAndTransposeIntMatrix(int numberOfRows)
    {
        int[][] matrix = ReadIntMatrix(numberOfRows); int[][] ret = new int[matrix[0].Length][];
        for (int i = 0; i < ret.Length; i++) { ret[i] = new int[numberOfRows]; for (int j = 0; j < numberOfRows; j++)ret[i][j] = matrix[j][i]; } return ret;
    }
    public static string[] ReadLines(int quantity) { string[] lines = new string[quantity]; for (int i = 0; i < quantity; i++)lines[i] = reader.ReadLine().Trim(); return lines; }
    public static void WriteArray<T>(IEnumerable<T> array) { writer.WriteLine(string.Join(" ", array)); }
    public static void Write(params object[] array) { WriteArray(array); }
    public static void WriteLines<T>(IEnumerable<T> array) { foreach (var a in array)writer.WriteLine(a); }
    private class SDictionary<TKey, TValue> : Dictionary<TKey, TValue>
    {
        public new TValue this[TKey key]
        {
            get { return ContainsKey(key) ? base[key] : default(TValue); }
            set { base[key] = value; }
        }
    }
    private static T[] Init<T>(int size) where T : new() { var ret = new T[size]; for (int i = 0; i < size; i++)ret[i] = new T(); return ret; }
    #endregion
}

Recording Episodes Java Solution

import java.io.*;
import java.util.*;

public class Solution {

  static class Graph {
    int[] ptr;
    int[] nxt;
    int[] suc;
    int index = 1;

    public Graph(int nodes, int egges) {
      ptr = new int[nodes];
      nxt = new int[egges];
      suc = new int[egges];
    }

    void add(int u, int v) {
      nxt[index] = ptr[u];
      ptr[u] = index;
      suc[index++] = v;
    }

    void reset() {
      index = 1;
      Arrays.fill(ptr, 0);
    }
  }

  static class TarjanSCC {
    public int count;
    boolean[] marked;
    int[] id;
    int[] low;
    int pre;
    Stack<Integer> stack;
    int n;

    public TarjanSCC(Graph g, int n) {
      this.n = n;
      marked = new boolean[n];
      stack = new Stack<Integer>();
      id = new int[n];
      low = new int[n];
      for (int v = 0; v < n; v++) {
        if (!marked[v]) {
          dfs(g, v);
        }
      }
    }

    void dfs(Graph g, int v) {
      int w;
      marked[v] = true;
      low[v] = pre++;
      int min = low[v];
      stack.push(v);
      for (int i = g.ptr[v]; i > 0; i = g.nxt[i]) {
        w = g.suc[i];
        if (!marked[w]) {
          dfs(g, w);
        }
        if (low[w] < min) {
          min = low[w];
        }
      }
      if (min < low[v]) {
        low[v] = min;
        return;
      }

      do {
        w = stack.pop();
        id[w] = count;
        low[w] = n;
      } while (w != v);
      count++;
    }

    public boolean stronglyConnected(int u, int v) {
      return id[u] == id[v];
    }
  }

  static class Sat2 {
    int n = 0;
    Graph edges = null;

    public Sat2(int n, Graph edges) {
      this.n = n;
      this.edges = edges;
      edges.reset();
    }

    public int c_not(int a) {
      return -a - 1;
    }

    int c_convert(int a) {
      return a < 0 ? (c_not(a) << 1) ^ 1 : a << 1;
    }

    void c_must(int a) {
      edges.add(a ^ 1, a);
    }

    void c_or(int a, int b) {
      edges.add(a ^ 1, b);
      edges.add(b ^ 1, a);
    }

    public void c_xor(int a, int b) {
      c_or(a, b);
      c_or(a ^ 1, b ^ 1);
    }

    void c_and(int a, int b) {
      edges.add(a, b);
      edges.add(b, a);
    }

    void c_not_and(int a, int b) {
      edges.add(a, b ^ 1);
      edges.add(b, a ^ 1);
    }

    public int not(int a) {
      return c_not(a);
    }

    public void must(int a) {
      c_must(c_convert(a));
    }

    public void or(int a, int b) {
      c_or(c_convert(a), c_convert(b));
    }

    public void xor(int a, int b) {
      c_xor(c_convert(a), c_convert(b));
    }

    public void and(int a, int b) {
      c_and(c_convert(a), c_convert(b));
    }

    public void notAnd(int a, int b) {
      c_not_and(c_convert(a), c_convert(b));
    }

    public boolean possible() {
      TarjanSCC scc = new TarjanSCC(edges, n*2);
      for (int v = 0; v < n; v++) {
        if (scc.stronglyConnected(v << 1, (v << 1) ^ 1)) {
          return false;
        }
      }
      return true;
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int q = Integer.parseInt(st.nextToken());

    int[][] se = new int[200][2];
    boolean[][] ol = new boolean[200][200];
    Graph edges = new Graph(200, 500);

    for (int itr = 0; itr < q; itr++) {
      st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());

      for (int i = 0; i < n; i++) {
        st = new StringTokenizer(br.readLine());
        int sl = Integer.parseInt(st.nextToken());
        int el = Integer.parseInt(st.nextToken());
        int sr = Integer.parseInt(st.nextToken());
        int er = Integer.parseInt(st.nextToken());
        se[i * 2][0] = sl;
        se[i * 2][1] = el;
        se[i * 2 + 1][0] = sr;
        se[i * 2 + 1][1] = er;
      }

      for (int i = 0; i < n * 2 - 1; i++) {
        for (int j = i + 1; j < n * 2; j++) {
          ol[i][j] = (se[i][0] <= se[j][1] && se[j][0] <= se[i][1]);
          ol[j][i] = ol[i][j];
        }
      }

      int ll = 0;
      int rr = 0;

      int l = ll;
      int r = rr;
      while (true) {
        Sat2 sat2 = new Sat2(n, edges);
        for (int x = l; x < r; x++) {
          for (int y = x + 1; y <= r; y++) {
            if (ol[x * 2][y * 2]) {
              sat2.or(x, y);
            }
            if (ol[x * 2 + 1][y * 2]) {
              sat2.or(sat2.not(x), y);
            }
            if (ol[x * 2][y * 2 + 1]) {
              sat2.or(x, sat2.not(y));
            }
            if (ol[x * 2 + 1][y * 2 + 1]) {
              sat2.or(sat2.not(x), sat2.not(y));
            }
          }
        }
        if (sat2.possible()) {
          if (r - l > rr - ll) {
            ll = l;
            rr = r;
          }
          if (r == n - 1) {
            break;
          }
          r++;
        } else {
          l++;
          if (r < l) {
            r = l;
          }
        }
      }

      bw.write((ll + 1) + " " + (rr + 1));
      bw.newLine();
    }

    bw.close();
    br.close();
  }
}

Recording Episodes Python Solution

#True if two intervals interesects
def has_intersection(I1,I2):
    if I1[0] >= I2[0] and I1[0] <= I2[1]: return True
    if I1[1] >= I2[0] and I1[1] <= I2[1]: return True
    if I2[0] >= I1[0] and I2[0] <= I1[1]: return True
    if I2[1] >= I1[0] and I2[1] <= I1[1]: return True
    return False

#Given the SAT Graph, return the longest interval with a dual-complete graph 
def max_range(G,GT):
    size = len(G)/4
    maxRange = [0,1]
    maxSize = 1

    a = 0
    b = 2

    while b <= size:
        SCC = []
        SCC = get_strong_connected_components(G,GT, a*4, b*4)
        newSize = b-a
        if is_satisfiable(SCC):
            if newSize > maxSize:
                maxRange = [a,b]
                maxSize = newSize
            b+=1
        else:
            if newSize == maxSize + 1:
                b+=1
            a+=1

    return maxRange

#Get the components only considering vertices between a (inclusive) and b (exclusive) indices
def get_strong_connected_components(G, GT, a, b):
    SCC = []
    numVertices = b-a
    compQueue = []
    Visited = [0 for c1 in range(numVertices)]
    for c1 in range(a,b):
        build_queue(G, a, b, compQueue, Visited, c1)
    while len(compQueue) > 0:
        i = compQueue.pop(-1)
        C = []
        build_component(GT, a, b, Visited, C, i)
        if len(C)>0: SCC.append(C)
    return SCC

def build_queue(G,a,b,compQueue, Visited, i):
    if Visited[i-a] == 1: return
    Visited[i-a] += 1

    for j in G[i]:
        if j>=a and j<b:
            build_queue(G, a, b, compQueue, Visited, j)
    compQueue.append(i)
    return

def build_component(GT, a, b, Visited, C, i):
    if Visited[i-a] == 2: return
    Visited[i-a] += 1
    for j in GT[i]:
        if j>=a and j<b:
            build_component(GT, a, b, Visited, C, j)
    C.append(i)
    return

    #returns False if for some a, a and not a are in the same component
def is_satisfiable(SCC):
    for C in SCC:
        C.sort()
        for c1 in range(len(C)-1):
            if C[c1+1]-C[c1] == 1 and C[c1]%2==0: return False
    return True

def build_digraph(S):
    size = len(S)*4
    G = []
    GT = []
    for c1 in range(size):
        G.append([])
        GT.append([])

    for c1 in range(len(S)):
        i = c1*4
        G[i+1].append(i+2)
        GT[i+2].append(i+1)
        G[i+3].append(i)
        GT[i].append(i+3)

    for c1 in range(len(S)):
        for c2 in range(2):
            i = c2*2
            tr1 = [S[c1][i],S[c1][i+1]]
            for c3 in range(c1, len(S)):
                for c4 in range(2):
                    if c1==c3 and c2==c4: continue
                    j = c4*2
                    tr2 = [S[c3][j],S[c3][j+1]]
                    if has_intersection(tr1,tr2):
                        k = c1*4
                        l = c3*4
                        G[k+i].append(l+j+1)
                        GT[l+j+1].append(k+i)
                        if c1!=c3:
                            G[l+j].append(k+i+1)
                            GT[k+i+1].append(l+j)

    return [G,GT]

    #main
q = int(input())
for c1 in range(q):
    n = int(input())
    S = []
    for c2 in range(n):
        s = input().split(' ')
        for c3 in range(len(s)):
            s[c3] = int(s[c3])
        S.append(s)
    G,GT = build_digraph(S)
    maxRange = max_range(G,GT)
    print(f'{maxRange[0]+1} {maxRange[1]}')
c C# C++ HackerRank Solutions java javascript python