**Segments( count of maximum no of overlaping segments that can be formed after rearranging segments )

Segments

A number of segments are lying on a line. Every segment is given with the coordinates of its endpoints. Segments are numbered from 1 to N (0 < N < 500). We assume, that one segment is inside another, if the two segments are different, the first one is fully contained in the second one, and their endpoints do not coincide. Write a program, which finds the numbers of the segments in the longest sequence of segments which are contained in. In the sequence, every segment except the last is inside the next segment in the sequence.

Input

The first line contains one integer N. Next, there are N lines, with two integers on every line, which are the coordinates of the left and the right endpoints of the corresponding segment. These coordinates are integers in the interval [–10000, 10000]. We assume that, the given segments are numbered according to their place in the input.

Output

The first line must contain one integer, equal to the number of segments in the found sequence. The following line must contain the numbers of the segments in this sequence. These numbers must be outputted, in the order in which the segments' lengths increase, starting from the smallest. If there are more than one output sequences, write any of them.

Sample

input	output
4 -2 2 -1 1 -3 3 4 5	3 2 1 3

Problem Author: Emil Kelevedzhiev
Problem Source: Winter Mathematical Festival Varna '2001 Informatics Tournament 

Tags: dynamic programming  (

 hide tags for unsolved problems

 )

-----------------------------------------------------editorial-------------------------------------------------------

WE CAN EASILY CALCULATE ANSWER , MAIN THING IS FIXING START , MEANS LOWEST SEGMENT DECISSION , SINCE CONSTRAINTS ARE VERY LOW SOO TRY ONE BY ONE CONSIDER EACH SESMENT AS A START SEGMENT ,  NOW IN  AND MANY PART FOR REST OF SEGMENT AS A START WILL BE COMPUTED IN THE FIRST CALL,

NOW MAIN THING IS BACKTRACKING , RECURSIVE BACKTRACKING WILL BE THE EASIEST BACKTRACKING IN THIS PROBLEM ,

---------------------------------------------CODE--------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

int dp[505];

vector<pair<int,int>  > v;

int n;

int  solve(int index)

 {

   if(index>=n) return 0;

   if(dp[index]!=-1) return dp[index];

   

   else

   {

     int xindex=v[index].first;

     int yindex=v[index].second;

     int ret=0;

    for(int i=0;i<n;i++)

     {

       if(v[i].first<xindex && v[i].second>yindex)

        {

         ret=max(ret,solve(i));

 }

     

   }

   dp[index]=ret+1;

   return dp[index];

  }

 }

 

 

 int cov=0;

   int ans=0;

 int print(int index)

  {

    if(index>=n) return 0;

    else if(cov==ans-1)

    {

     cout<<index+1<<endl;

     return 0;

   }

    else

     { 

int xindex=v[index].first;

     int yindex=v[index].second;

   

    for(int i=0;i<n;i++)

     {

       if(v[i].first<xindex && v[i].second>yindex && solve(index)==solve(i)+1)

        {

         cout<<index+1<<" ";

         cov++;

          print(i);

          break;

 }

     

   }

}

  }

 int main()

  {

    

     cin>>n;

     for(int i=0;i<n;i++)

      {

        int a,b;

         cin>>a>>b;

         v.push_back(make_pair(a,b));

 }

 for(int i=0;i<=n;i++) dp[i]=-1;

 for(int i=0;i<n;i++)

  {

     ans=max(ans,solve(i));

  }

     

       cout<<ans<<endl;

       for(int i=0;i<n;i++)

        {

          if(dp[i]==ans)

          {

           print(i);

           break;

 }

}

 

 return 0;

  }