TRAINING problem CodeChef

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.NavigableMap;
import java.util.PriorityQueue;
import java.util.TreeMap;

class SelectionForTrainingCamps {

    public static void main( final String[] args ) throws Exception {
        final BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
        final int T = toi( br.readLine() );
        for ( int ii = 0; ii < T; ii++ ) {
            final int N = toi( br.readLine() );
            final int[] w = new int[ N ];
            final int[] h = new int[ N ];
            for ( int i = 0; i < h.length; i++ ) {
                final int[] t = toi( br.readLine().split( " " ) );
                w[i] = t[0];
                h[i] = t[1];
            }
            System.out.println( solve( N, w, h ) );
        }
    }

    public static String solve( final int n, final int[] w, final int[] h ) {
        // initialization
        final TreeMap<Integer, PriorityQueue<Kid>> ws = new TreeMap<Integer, PriorityQueue<Kid>>(); // tree sorted by weight
        final Kid[] kids = new Kid[ n ];
        for ( int i = 0; i < w.length; i++ ) {
            kids[i] = new Kid( w[i], h[i] );
            PriorityQueue<Kid> pq = ws.get( w[i] );
            if ( pq == null ) pq = new PriorityQueue<Kid>( 128, Collections.reverseOrder() );
            pq.add( kids[i] );
            ws.put( w[i], pq );
        }
        Arrays.sort( kids ); // order by height, decreasing

        final StringBuilder buff = new StringBuilder();
        int teams = 0;
        for ( int i = 0; i < kids.length; i++ ) { // iterate kids by decreasing height O(N)
            if ( kids[i].inTeam ) continue;
            ++teams;
            // manage team captain = the kid first in team
            kids[i].inTeam = true;
            {
                final PriorityQueue<Kid> pq = ws.get( kids[i].w );
                pq.poll();
                if ( pq.isEmpty() ) {
                    ws.remove( kids[i].w );
                }
            }
            int cnt = 1; // captain
            // get all kids with greater weight - O(log(N))
            final NavigableMap<Integer, PriorityQueue<Kid>> gw = ws.tailMap( kids[i].w, false );
            final LinkedList<Integer> toRemove = new LinkedList<Integer>();
            for ( final int weight : gw.keySet() ) { // this loop runs max O(N) times together
                final PriorityQueue<Kid> pq = gw.get( weight );
                final Kid kid = pq.poll();
                if ( pq.isEmpty() ) toRemove.add( weight );
                kid.inTeam = true;
                ++cnt;
            }
            for ( final int key : toRemove ) {
                ws.remove( key );
            }
            buff.append( ' ' ).append( cnt );
        }
        buff.replace( 0, 1, teams + "\n" );
        return buff.toString();
    }

    static class Kid implements Comparable<Kid> {
        int w;
        int h;
        boolean inTeam = false;

        public Kid(final int w, final int h) {
            this.w = w;
            this.h = h;
        }

        @Override
        public int compareTo( final Kid k ) {
            return -Integer.valueOf( this.h ).compareTo( k.h );
        }
    }

    public static int[] toi( final String... sa ) {
        final int[] res = new int[ sa.length ];
        for ( int i = 0; i < res.length; i++ )
            res[i] = Integer.parseInt( sa[i] );
        return res;
    }

    public static int toi( final String s ) {
        return Integer.parseInt( s );
    }
}