1:
2: #include <queue>
3: #include <iostream>
4: #include <string.h>
5: #include <stdio.h>
6: using namespace std;
7: #define V 505 // vertex
8: #define INF 0x3F3F3F3F
9: int N;
10: int dis[V][V];
11: int path[V][V];
12:
13: // normal distance.
14: void floyd()
15: {
16: for(int k=1;k<=N;k++)
17: {
18: for(int i=1;i<=N;i++)
19: {
20: for(int j=1;j<=N;j++)
21: {
22: if(dis[i][k]== -INF || dis[k][j] == -INF) continue;
23: if(dis[i][k] + dis[k][j] > dis[i][j])
24: {
25: dis[i][j] = dis[i][k] + dis[k][j];
26: path[i][j] = path[i][k];
27: }
28:
29: }
30: }
31: }
32: }
33: void floyd_path(int i, int j)
34: {
35: int k=path[i][j];
36: while(k!=j)
37: {
38: printf(" %d", k );
39: k= path[k][j];
40: }
41: }
42:
43: int main()
44: {
45: //freopen("1078.txt","r",stdin);
46: scanf("%d", &N);
47: int a, b;
48: vector<pair<int, int> > C;
49: memset(dis, 0 ,sizeof(dis));
50: for(int i=0; i<N; i++)
51: {
52: scanf("%d%d", &a, &b);
53: C.push_back(make_pair(a,b));
54: for(int i=0; i<C.size(); i++)
55: {
56: if(a<C[i].first && b> C[i].second)
57: {
58: dis[i+1][C.size()] = 1;
59: path[i+1][C.size()] = C.size();
60: }
61: else if(a> C[i].first && b< C[i].second)
62: {
63: dis[C.size()][i+1]=1;
64: path[C.size()][i+1] = i+1;
65: }
66: }
67: }
68: for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) if(dis[i][j]==0) dis[i][j]=-INF;
69: floyd();
70: int ret = 0;
71: for(int i=1; i<=N; i++)
72: {
73: for(int j=1; j<=N; j++)
74: {
75: if(dis[i][j] > ret)
76: {
77: ret = dis[i][j];
78: a = i; b = j;
79: }
80: }
81: }
82: if(ret == 0)
83: {
84: cout<<1<<endl;
85: cout<<1<<endl;
86: }else
87: {
88: cout<<ret+1<<endl;
89: cout<<a;
90: floyd_path(a,b);
91: cout<<" "<<b<<endl;
92: }
93: return 0;
94: }
95: