UVa 12086:Potentiometers

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;



int POT[200005],tree[524300],record[524300];

void initialize(int begin,int end,int node)
{
    if(begin==end){tree[node]=POT[begin];record[begin]=node;}


    else { int mid=(begin+end)/2;

                initialize(begin,mid,2*node);
                initialize(mid+1,end,2*node+1);
                tree[node]=tree[2*node]+tree[2*node+1];


               }
}

long long int query(int i,int j,int begin,int end,int node)
{
    int p1,p2;

    if(end<i || j<begin)return 0;

    if(i<=begin && end<=j)return tree[node];

    else {int mid=(begin+end)/2;
             p1=query(i,j,begin,mid,2*node);
              p2=query(i,j,mid+1,end,2*node+1);
              return p1+p2;
                }
}

void update(int index,int val,int begin,int end,int node)
{
   int n=record[index];
   tree[n]=val;
   n/=2;
   while(n>0)
     {
         tree[n]=tree[2*n]+tree[2*n+1];
         n/=2;
     }
}
int main()
{
    int pot,t=1;
  bool blank=false;
    while(scanf("%d",&pot)==1)
    {if(!pot)break;
        int i;

        for(i=0;i<pot;i++)
          scanf("%d",&POT[i]);
       if(blank)printf("\n");
       char command[5];
       //getchar();

       initialize(0,pot-1,1);

      /* for(i=1;i<50;i++)
       {
           cout<<"NODE "<<i<<" i"<<tree[i]<<endl;
       }*/
      // cout<<"hoise"<<endl;
      printf("Case %d:\n",t);
      t++;


       while(true)
 {
     scanf("%s",&command);
     if(strcmp("END",command)==0)break;
     else if(strcmp(command,"M")==0){int a,b;
                                                               scanf("%d%d",&a,&b);
                                                                if(a>b)swap(a,b);


                                                              printf("%d\n",query(a-1,b-1,0,pot-1,1));
                                                                //getchar();
                                                                }

      else if(strcmp(command,"S")==0){int val,index;
                                                               scanf("%d%d",&index,&val);
                                                                update(index-1,val,0,pot-1,1);
                                                                 }
     //else if(command=="S")
 }
    if(blank==false)blank=true;
    }

}

UVa 10004:Bicoloring

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>

using namespace std;


int node,edge;

bool bfs()
{

    vector<int>adjlist[1000];

    int i;
    for(i=0;i<edge;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        adjlist[x].push_back(y);
        adjlist[y].push_back(x);

    }

    queue<int>BFS;

    int colour[1000],cur=1;  //1=white,-1=black
    bool visited[1000];


    memset(visited,false,sizeof(visited));

    BFS.push(0);
    visited[0]=true;
    colour[0]=1;



    while(!BFS.empty())
    { int f=BFS.front();
      //cout<<f<<"curnode"<<endl;
        cur*=-1;
        for(i=0;i<adjlist[f].size();i++)
          {  int C=adjlist[f][i];
          //cout<<C<<"child"<<endl;
              if(visited[C]==true){
                                               if(colour[C]==colour[f])return false;
                                               }
              else { visited[C]=true;
              BFS.push(C);
                       colour[C]=colour[f]*-1;

              }

          }

          BFS.pop();

    }
    return true;
    }

int main()
{

    while(cin>>node)
    {
        if(node==0)break;


        cin>>edge;

        bool bicolour=bfs();
        if(bicolour)cout<<"BICOLORABLE."<<endl;
        else cout<<"NOT BICOLORABLE."<<endl;
    }
}

UVa-336::A Node Too Far

#include<cstdio>
#include<iostream>
#include<map>
#include<queue>
#include<cstring>
using namespace std;


int main()
{ int T=0;
    while(true){
                        int edge;
                        cin>>edge;
                        if(edge==0)break;
                        map<int,int>graph;
                        int a,b,i,j,tot=1;

                        vector<int>adjlist[110];



                        while(edge--){cin>>a>>b;
                                                if(graph[a]==0){graph[a]=tot++;
                                                          //cout<<tot<<"TOT"<<endl;
                                                                           }
                                                if(graph[b]==0){graph[b]=tot++;
                                                           //cout<<tot<<"TOT"<<endl;
                                                                        }
                                                int p=graph[a],q=graph[b];
                                                //          cout<<p<<" "<<q<<endl;
                                                adjlist[p].push_back(q);
                                                adjlist[q].push_back(p);


                                               }
                            //map<int,int>::iterator it;
                                //for(it=graph.begin();it!=graph.end();it++)cout<<(*it).first<<" "<<(*it).second<<endl;
                            /*for(i=1;i<tot;i++)
                                            {
                                                cout<<i<<" contains "<<(int)adjlist[i].size()<<" nodes"<<endl;
                                            }
*/
/*BFS*/

                            int source,ttl;
                            while(cin>>source>>ttl )
                                            {
                                            if(source+ttl==0)break;

                                            bool visited[1010];
                                            int distance[1010];
                                            queue<int>BFS;

                                            memset(visited,false,sizeof(visited));
                                            memset(distance,-1,sizeof(visited));


                                            distance[graph[ source]  ]=0;
                                            visited[graph[source]]=true;
                                            BFS.push(graph[source]);
                                            while(!BFS.empty())
                                                        {
                                                             int f=BFS.front();
                                                             // cout<<"F "<<f<<endl;
                                                              for(int i=0;i<adjlist[f].size();i++)
                                                                        { int v=adjlist[f][i];

                                                                            if(visited[v]==false)
                                                                                                {  //cout<<"V "<<v<<endl;
                                                                                                    distance[v]=distance[f]+1;
                                                                                                    visited[v]=true;
                                                                                                    BFS.push(v);
                                                                                                }

                                                                        }

                                                        BFS.pop();
                                                        }

int TOTAL=0;
for(int i=1;i<tot;i++)
  {
      if(distance[i]>ttl || distance[i]==-1)TOTAL++;
  }
cout<<"Case "<<++T<<": "<<TOTAL<<" nodes not reachable from node "<<source<<" with TTL = "<<ttl<<"."<<endl;
}



                        }


}

UVa-1180:Perfect Numbers

#include<cstdio>
#include<iostream>
#include<cmath>

#define MAX 1<<26

bool check(int N,int pos)
{
return   (bool) (N & (1<<pos));

}
int set(int N,int pos)
{return  N | (1<<pos);

}

using namespace std;

int bitsieve[(MAX>>5)+2];
void sieve()
{
   int i,j,n;
    n=(int) sqrt(MAX);
   for(i=3;i<=n;i+=2)
     {
         if(check(bitsieve[i>>5],i&31)==0)
         {//cout<<i<<"prime"<<endl;


           for(j=i*i;j<=MAX;j+=i<<1)
             {
                 bitsieve[j>>5]=set(bitsieve[j>>5],j&31);
             }

             }

     }

}


int main()
{
    sieve();

}

UVa-496 Simply subsets

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>

using namespace std;

#define MAX 1000
int M,N,LCS[1000+5][1000+5];

class set{
    public:
int element[MAX];
int card;
};

int lcs(set A,set B)
{ int M=A.card,N=B.card;
int i,j;
for(i=0;i<1005;i++)LCS[i][0]=0;
for(j=0;j<1005;j++)LCS[0][j]=0;

for(i=1;i<=M;i++)
    for(j=1;j<=N;j++)
    {
        if(A.element[i-1]==B.element[j-1])LCS[i][j]=LCS[i-1][j-1]+1;
      else LCS[i][j]=max(LCS[i-1][j],LCS[i][j-1]);
    }
return LCS[M][N];
}
void print(int res,int M,int N)
{  if(res==0)cout<<"A and B are disjoint"<<endl;
    else if(M!=N){if(res==M)cout<<"A is a proper subset of B"<<endl;
                    else if(res==N)cout<<"B is a proper subset of A"<<endl;
                    else cout<<"I'm confused!"<<endl;
                    }
     else if(M==N){if(res==M)cout<<"A equals B"<<endl;
                    else cout<<"I'm confused!"<<endl;

                      }
      return ;
}


int main()
{
    while(1){ set S[2];
                  M=N=0;
                    char inp1[MAX],inp2[MAX];
                    gets(inp1);
                    if(feof(stdin))break;
                    char *p1;
                    p1=strtok(inp1," ");
                     while(p1!=NULL){ S[0].element[M++]=atoi(p1);
                                                    p1=strtok(NULL," ");
                                                    }
                                                    S[0].card=M;

                    gets(inp2);
                    char *p2;
                    p2=strtok(inp2," ");
                     while(p2!=NULL){ S[1].element[N++]=atoi(p2);
                                                    p2=strtok(NULL," ");
                                                    }
                                                    S[1].card=N;
                       sort(S[0].element,S[0].element+M);
                       sort(S[1].element,S[1].element+N);
                       int res=lcs(S[0],S[1]);

                       print(res,M,N);
                       }
                       return 0;
}

UVa-482 Permutation arrays

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;


class array{
public:int i;
string num;
};

bool comp(array a,array b)
{
    if(a.i<b.i)return true;
    else return false;
}
int main()
{ int test;
scanf("%d",&test);
array a[1000];
bool blank=false;
getchar();
while(test--){char input[100000];

                    gets(input);
                     gets(input);
                     char *point;
                     int index1=0,index2=0;
                    point=strtok(input, " ");
                    while(point!=NULL){a[index1++].i=atoi(point);
                                                        point=strtok(NULL, " ");

                                                        }
                                   gets(input);
                           point=strtok(input," ");
                    while(point!=NULL){a[index2++].num=point;
                                                        point=strtok(NULL," ");
                                                        }
                    sort(a,a+index1,comp);
                    if(blank)cout<<endl;
                    blank=true;
                    for(int I=0;I<index1;I++)cout<<a[I].num<<endl;
                           }

}

UVa-10131 Is bigger smarter?

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;
#define MAX 10000
int I,len[MAX],pre[MAX],output[MAX],i,j,maX,highest;


class elephant{
public:
int iq,weight,index;
};

bool comp(elephant a,elephant b)
{
    if (a.iq>=b.iq)return true;
    else return false;
}



int main()
{
    int W,IN=0;
    I=0;
    elephant ele[MAX];
    while(scanf("%d %d",&W,&IN)!=EOF)
    {ele[I].weight=W;
      ele[I].iq=IN;
      ele[I].index=I+1;
      I++;

    }
    sort(ele,ele+I,comp);
    //int res=lis(I);
    for(i=0;i<I;i++){pre[i]=i;len[i]=1;}
    for(i=0;i<I-1;i++)
       for(j=i+1;j<I;j++)
           {
                    if(ele[i].weight<ele[j].weight && len[i]+1>len[j]){len[j]=len[i]+1;pre[j]=i;}
           }
     maX=0;
     for(i=0;i<I;i++)if(maX<len[i]){maX=len[i];highest=i;}
     cout<<maX<<endl;
//output
for(i=maX;i>0;i--){output[i]=highest;
                                 highest=pre[highest];
                                 }
         for(i=1;i<=maX;i++)cout<<ele[output[i]].index<<endl;
 
  return 0;
}

UVa-497 Strategic Defense Initiative

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;

#define MAX 10000

int len[MAX+5],pre[MAX+5],seq[MAX+5],output[MAX+10];
int N,maX,highest;

int lis(int N)
{
    int i,j;
    for(i=0;i<N;i++)len[i]=1;

    for(i=0;i<N;i++)
       for(j=i+1;j<N;j++){if(seq[j]>seq[i]){ if(len[i]+1>len[j]){len[j]=len[i]+1;
                                                                                                   pre[j]=i;
                                                                                                      }

                                                                     }
       }
       maX=0;
   for(i=N-1;i>=0;i--){if(maX<len[i]){maX=len[i];highest=i;}
                                      }

       return maX;
}

void printlcs()
{  output[maX]=seq[highest];
    for(int i=maX-1;i>0;i--){ output[i]=seq[pre[highest]];
                                               highest=pre[highest];
                                                  }
for(int i=1;i<=maX;i++)cout<<output[i]<<endl;

return ;
}


int main()
{
    int tc,t=0;
    scanf("%d",&tc);
    getchar();
    char ch[20];
    bool blank=false;

    gets(ch);
    while(tc--){int I=0;
    while(gets(ch) &&strlen(ch))
    {

         //puts(ch);
                                                     int J=atoi(ch);
                                                     seq[I++]=J;
                                                     //cout<<J<<endl;




    }
    //cout<<I<<endl;
    if(blank)cout<<endl;
    blank=true;
    int res=lis(I);
    printf("Max hits: %d\n",res);
    printlcs();

}
return 0;
}

UVa-231 Testing the catcher

#include<cstdio>
#include<iostream>
#include<algorithm>
#define INF 20000000000
#define MAX 10000

using namespace std;

int seq[MAX+1],len[MAX+5],n;

int lis(int n)
{ int i,j;
    for(i=0;i<n;i++)len[i]=1;
   for(i=0;i<n;i++){
       for(j=i+1;j<n;j++)
          {
              if(seq[j]>=seq[i]){if(len[i]+1>len[j])len[j]=len[i]+1;}
          }

                                 }
                                // for(i=0;i<n;i++)cout<<len[i]<<" ";
                                 //cout<<endl;
                                 int maX=*max_element(len,len+n);
                                 return maX;
}


int main()
{ int tc=1,signal=false;
   while(1){
               mylabel:

                int I=0;
                while(1){
                        scanf("%d",&seq[I]);
                        if(seq[I]==-1)break;
                        seq[I]=-1*seq[I];
                        I++;


                                }

                if(seq[0]==-1)break;
                 if(signal)cout<<endl;
                n=I;
                int result=lis(n);
                //printf("%d %d\n",tc,result);
                printf("Test #%d:\n",tc);
                cout<<"  maximum possible interceptions: "<<result<<endl;
                signal=true;
                tc++;
                goto mylabel;
                }
}

UVa-11151 Longest Pallindrome

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>

#define MAX 1005

char inp[MAX],revinp[MAX];
int c[MAX][MAX];

using namespace std;

int pal(char *inp)
{
    int M=strlen(inp);

    strcpy(revinp,inp);
    reverse(revinp,revinp+M);


    int i,j;
    for(int i=1;i<=M;i++)c[i][0]=0;
    for(int j=0;j<=M;j++)c[0][j]=0;

    for(i=1;i<=M;i++)
        for(j=1;j<=M;j++)
           {
               if(inp[i-1]==revinp[j-1])c[i][j]=c[i-1][j-1]+1;
               else if(c[i-1][j]>=c[i][j-1])c[i][j]=c[i-1][j];
               else c[i][j]=c[i][j-1];
           }
           return c[M][M];
}
int main()
{
    int tc;
    bool signal=false;
    cin>>tc;
    tc+=1;

        while(tc--){ int len;

                                                //scanf("%s",&inp);
                       gets(inp);
                        if(signal==false){signal=true;continue;}

                       if(strcmp("\n",inp)==0)len=0;
                       else  len=pal(inp);
                      cout<<len<<endl;
                     }
                    return 0;

}

UVa-10036 Divisiblity

#include<iostream>
#include<cstdio>
#define MAX 10001
#define MAX2 100

using namespace std;
int N,K;
int A[MAX];
bool result[MAX][MAX2],count[MAX][MAX2];

void init()
{
    int i,j;
    for(i=0;i<MAX;i++)
        for(j=0;j<MAX2;j++)
            count[i][j]=false;
            return ;
}

bool div(int n,int k)
{  //printf("Calling(%d %d)\n",n,k);
   if(count[n][k]==true)return result[n][k];
    int k1=A[n]%K;
    if(k1<0)k1=K+k1;


    if(n==1 ){ if( (k1==k) || ( (K-k1)%K ==k) )return true;
                       else return false;
                      }
     bool c,d;
     c=div(n-1,(k+k1)%K );
     count[n-1][(k+k1)%K]=true;
     result[n-1][(k+k1)%K]=c;

          //printf("calling 1 ( %d %d),result %d\n",n-1,(A[n] %K),c);

     d=div(n-1,(k-k1)%K);
     count[n-1][(k-k1)%K]=true;
     result[n-1][(k-k1)%K]=d;
     //printf("calling 2( %d %d),result %d \n",n-1,(A[n] %K),d);
          if( c==true || d==true) return true;
     else return false;

}
int main()
{
    int tc;
    cin>>tc;
    while(tc--){  init();
                         cin>>N>>K;
                        for(int i=1;i<=N;i++)cin>>A[i];
                        //for(int i=1;i<=N;i++)cout<<A[i];

                        if(div(N,0))cout<<"Divisible"<<endl;
                        else cout<<"Not divisible"<<endl;




    }
}

UVa-191 :Intersection

#include<iostream>
#include<algorithm>
using namespace std;


class Point{

public:
int x,y;
void input(int a,int b);

};


void Point:: input(int a,int b)
{  x=a;
   y=b;

return ;
}

int cross(Point pi,Point pj,Point pk)
{  int a,b;
//cout<<"calling cross"<<endl;
    a=(pk.x-pi.x)*(pj.y-pi.y);
    b=(pj.x-pi.x)*(pk.y-pi.y);
    return a-b;

}

bool onsegment(Point pi,Point pj,Point pk)
{
    int minx=min(pi.x,pj.x),maxx=max(pi.x,pj.x),miny=min(pi.y,pj.y),maxy=max(pi.y,pj.y);

    if((minx<=pk.x) && (pk.x<=maxx) && (miny<=pk.y) && (pk.y<=maxy)) return true;
    //cout<<minx<<maxx<<maxy<<miny;
    //if(minx<=pk.x &(pk.x<=maxx) )return true;
    else return false;


}
bool intersect(Point P1,Point P2,Point P3,Point P4)
 {   long int d1,d2,d3,d4;
    d1=cross(P3,P4,P1);
    //cout<<"d1"<<d1<<endl;

    d2=cross(P3,P4,P2);
    //cout<<"d2"<<d2<<endl;

    d3=cross(P1,P2,P3);
    //cout<<"d3"<<d3<<endl;
    d4=cross(P1,P2,P4);
    //cout<<"d4"<<d4<<endl;
    if(((d1>0&&d2<0) || (d1<0&&d2>0) )&& ((d3>0&&d4<0)||(d3<0&&d4>0))) return true;
    else if (d1==0 && onsegment(P3,P4,P1)) return true;
    else if(d2==0 && onsegment(P3,P4,P2))return true;
     else if(d3==0 && onsegment(P1,P2,P3))return true;
    else if(d4==0 &&onsegment(P1,P2,P4))return true;

    else return false;}

bool onrect(int ax,int ay,int bx,int by,int Px,int Qy,int Rx,int Sy)
{  bool AX,AY,BX,BY;
  AX=AY=BX=BY=false;
     if(min(Px,Rx)<ax && ax<max(Px,Rx))AX=true;
     if(min(Qy,Sy)<ay &&ay<max(Qy,Sy))AY=true;
      if(min(Px,Rx)<bx && bx<max(Px,Rx))BX=true;
     if(min(Qy,Sy)<by &&by<max(Qy,Sy))BY=true;
     if(AX && AY && BX && BY==true)return true;
     else return false;

}

int main()
{  int tc,t=0;
cin>>tc;
    while(tc--){
    Point Ple,Pbe,P1,P2,P3,P4;
    int xle,yle,xbe,ybe,xleft,ytop,xright,ybottom;
    cin>>xle>>yle>>xbe>>ybe>>xleft>>ytop>>xright>>ybottom;
    bool b=onrect(xle,yle,xbe,ybe,xleft,ytop,xright,ybottom);

    Ple.input(xle,yle);
    Pbe.input(xbe,ybe);

     P1.input(xleft,ytop);
    P2.input(xleft,ybottom);
    P3.input(xright,ybottom);
    P4.input(xright,ytop);
   if(intersect(Ple,Pbe,P1,P2)==true)cout<<"T"<<endl;
   else if(intersect(Ple,Pbe,P2,P3)==true)cout<<"T"<<endl;
      else if (intersect(Ple,Pbe,P3,P4)==true)cout<<"T"<<endl;
   else if(intersect(Ple,Pbe,P4,P1)==true)cout<<"T"<<endl;
   else if(b==true)cout<<"T"<<endl;
   else cout<<"F"<<endl;
   //cout<<"Case :"<<++t<<endl;
   }

    return 0;
}

UVA-116 Undirectional TSP

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

#define MAXR 10
#define MAXC 100

using namespace std;



int main()
{
    int m,n;//row column
    int array[MAXR][MAXC],mini[MAXR][MAXC],child[MAXR][MAXC];//entry,minimum sum, path



    while(cin>>m>>n){if(feof(stdin))break;

                                 int i,j;//iterator

                                 for(i=0;i<m;i++)
                                        for(j=0;j<n;j++)cin>>array[i][j];  //array entry


                                 for(i=0;i<m;i++){mini[i][n-1]=array[i][n-1];}
                                   
                                for(j=n-2;j>=0;j--)            //dp apply +child set
                                     for(i=0;i<m;i++)
                                                          {
                                                            mini[i][j]=mini[(m+i-1)%m][j+1];
                                                            child[i][j]=(m+i-1)%m;

                                                          if(mini[i][j]>mini[i][j+1]){mini[i][j]=mini[i][j+1];
                                                                                                child[i][j]=i;
                                                                                              }
                                                         else if(mini[i][j]==mini[i][j+1] && child[i][j]>i)child[i][j]=i;

                                                    if(mini[i][j]>mini[(m+i+1)%m][j+1])
                                                                    {mini[i][j]=mini[(m+i+1)%m][j+1];
                                                                     child[i][j]=(m+i+1)%m;
                                                                     }
                                                   else if(mini[i][j]==mini[(m+i+1)%m][j+1] && child[i][j]>(m+i+1)%m)
                                                                      child[i][j]=(m+i+1)%m;

                                                     mini[i][j]+=array[i][j];
                                                         }


                    int minimum=30000000,minirow;
                    for(i=0;i<m;i++)if(minimum>mini[i][0]){minimum=mini[i][0];
                                                                               minirow=i;
                                                                               }   //minimum sum and source find

                    vector<int>path;
                    bool blank =false;

                    for(j=0;j<n;j++){path.push_back(minirow+1);                 //path ready+print
                                              if(blank)cout<<" ";
                                               cout<<path[j];
                                              minirow=child[minirow][j];
                                              blank=true;
                                              }


                    cout<<endl;


                    cout<<minimum<<endl;
                    }
   return 0;
}

UVA-108 Maximum sum

#include<cstdio>
#include<iostream>
#include<queue>

#define INF 30000
#define MAX 100

using namespace std;

int main()
{  int array[MAX][MAX];
   int sum[MAX][MAX][MAX];
 while(1){ int N;
           cin>>N;
           if(feof(stdin))break;
         
           priority_queue<int>pq;
           int i,j,k;

           for(i=0;i<N;i++)
               for(j=0;j<N;j++){cin>>array[i][j];          //array input
                                         pq.push(array[i][j]);} //to handle the case of all negative entries

         
            for(i=0;i<N;i++)                         // taking input for column combination sums
               for(j=0;j<N;j++){sum[i][j][j]=array[i][j];
                                           for(k=j+1;k<N;k++)sum[i][j][k]=sum[i][j][k-1]+array[i][k];
                                         }
       
          int Sum,maxsum=-INF;
          for(j=0;j<N;j++)
              for(k=j;k<N;k++){Sum=0;
                                         for(i=0;i<N;i++){Sum+=sum[i][j][k];
                                                                    if(Sum<0){Sum=0;}
                                                                    else if(Sum>=maxsum){maxsum=Sum;}
                                                                  }
                                           }
       
          if(maxsum==-INF)maxsum=pq.top();
          cout<<maxsum<<endl;

  }
  return 0;
}

UVA-103 Stacking Boxes

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

int totalbox,DIM;
int len[32],order[32],pred[32];
class box{
int dim[12];
public:
void input();             //taking input
void dimsort();        //dimension sorting
int operator<<(box BOX1);  //lexico sorting;
int operator>(box BOX1);    //lis compare
box operator^(box &BOX1);  //swap box's
};

void box::input()
{
    int i;
    for(i=1;i<=DIM;i++)cin>>dim[i];

    return;
}

void box::dimsort()
{ sort(dim+1,dim+1+DIM);
  return;
}

int box::operator<<(box BOX1)
{ int i;
  for(i=1;i<=DIM;i++){if(dim[i]<BOX1.dim[i])return 1;
                                    if(dim[i]>BOX1.dim[i])return 0;
                                  }
  return 0;
}

int box::operator>(box BOX1)
{ int i;
  for(i=1;i<=DIM;i++)if(dim[i]<=BOX1.dim[i])return 0;
  return 1;
 }

box box::operator^(box &BOX1)
{
    int i;
    for(i=1;i<=DIM;i++)swap(dim[i],BOX1.dim[i]);
    return *this;
}
void setvalue()
{
   int i;
   for(i=1;i<=totalbox;i++){order[i]=i;len[i]=1;
                         
                           }

   return;
}

 int main()
 {   int signal=0;
     while(cin>>totalbox>>DIM)
    {   if(signal)cout<<endl;
        box BOX[32];
        int i,j;
        setvalue();
        for(i=1;i<=totalbox;i++){BOX[i].input();
                                              BOX[i].dimsort();
                                             }

        for(i=1;i<totalbox;i++)
                    for(j=i+1;j<=totalbox;j++)
                                             if(BOX[j]<<BOX[i]){ BOX[j]^BOX[i];
                                                                                swap(order[j],order[i]);
                                                                               }
                             
                               
       
         for(i=1;i<totalbox;i++)
           for(j=i+1;j<=totalbox;j++){ if(BOX[j]>BOX[i] && len[i]+1>len[j]){len[j]=len[i]+1;
                                                                                                                    pred[j]=i;
                                                                                                                   }
                                                     }

            int max=0,maxel;;
            for(i=1;i<=totalbox;i++)if(max<len[i]){max=len[i];maxel=i;}
          int rev[32];
            rev[max]=order[maxel];
            for(i=max-1;i>0;i--){ rev[i]=order[pred[maxel]];
                                            maxel=pred[maxel];
                                            }
         
            cout<<max<<endl;
            cout<<rev[1];
            for(i=2;i<=max;i++)cout<<" "<<rev[i];
            cout<<endl;
            signal=1;

    }
    return 0;
    }