It is right....
I failed in #8 as well...
Look at this:
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.

Pay attention to this:
and their endpoints do not coincide.
It means
3 4 and 4 4 coincide too!

this helps even for WA#3

still wa

I also had WA#3, but this test is AC. My solution used BFS. Please, help me! Thanks!

#pragma comment(linker,"/STACK:8000000")
#include <stdio.h>

int loading(int &N,int** (&M)){
    int *Left,*Right;
    scanf("%d",&N);
    if(N==0) {printf("%d",0); return -1;}
    Left=new int[N]; Right=new int[N];
    int tmpL,tmpR;
    for(int i=0;i<N;++i) {scanf("%d %d",&tmpL,&tmpR); /*if(tmpR<tmpL) {int tmp=tmpR; tmpR=tmpL; tmpL=tmp;}*/ Left[i]=tmpL; Right[i]=tmpR;}

    M=new int*[N];
    for(int i=0;i<N;++i) {M[i]=new int[N]; for(int j=0;j<N;++j) M[i][j]=0;}

    //i-ый отрезок вложен в j-ый
    for(int i=0;i<N;++i) for(int j=0;j<N;++j) if(Left[j]<Left[i] && Right[i]<Right[j]) {M[i][j]=1; M[j][i]=-1;}

    delete[] Left;delete[] Right;
    return 0;
}


int doing(int &N,int **(&M),int *(&Last),int &posBiggestWeight,int &BiggestWeight){
    Last=new int[N];
    int *Weight=new int[N];
    for(int i=0;i<N;++i) {Last[i]=-1; Weight[i]=0;}

    //Поиск отрезков, которые ни во что не вложены
    int *Roots=new int[N],iCountRoots=0;
    for(int i=0;i<N;++i){
        bool isNotRoot=true;
        for(int j=0;j<N && isNotRoot;++j) if(M[i][j]==1) isNotRoot=false;
        if(!isNotRoot){
            Roots[iCountRoots++]=i;
        }
    }

    //Перебор всех вложеных
    for(int k=0;k<iCountRoots;++k){
        int NeedVisit[1000000],cntNVisit=0;
        NeedVisit[cntNVisit++]=Roots[k]; Weight[Roots[k]]=0;
        while(cntNVisit>0){
            int tekVertex=NeedVisit[--cntNVisit],tekWeight=Weight[tekVertex],newWeight=tekWeight+1;
            for(int j=0;j<N;++j) if(M[tekVertex][j]==1 && newWeight>=Weight[j]){
                NeedVisit[cntNVisit++]=j; Weight[j]=newWeight; Last[j]=tekVertex;
            }
        }
    }
    //поиск максимального веса
    BiggestWeight=-2; posBiggestWeight=-1;
    for(int i=0;i<N;++i) if(Weight[i]>BiggestWeight){
        posBiggestWeight=i; BiggestWeight=Weight[i];
    }
    delete[] Weight;
    return 0;
}

int saveing(int &N,int* (&Last),int &posBiggestWeight,int &BiggestWeight){
    int *Answer=new int[BiggestWeight+1],pos=posBiggestWeight;
    int indAnswer=BiggestWeight;
    while(pos!=-1){
        Answer[indAnswer--]=pos+1; pos=Last[pos];
    }
    printf("%d\n",BiggestWeight+1);
    for(int i=0;i<BiggestWeight;++i) printf("%d ",Answer[i]); printf("%d\n",Answer[BiggestWeight]);
    delete[] Answer;
    return 0;
}

int main(){
    int N,**M,*Last,posBiggestWeight=0,BiggestWeight=0;
    int res=loading(N,M);
    if(res==-1) return 0;
    doing(N,M,Last,posBiggestWeight,BiggestWeight);
    saveing(N,Last,posBiggestWeight,BiggestWeight);

    delete[] Last;
    for(int i=0;i<N;++i) delete[] M[i];
    delete[] M;

    return 0;
}

At last! AC 0.001 and 394 KB