#include #include #include #include #include #include #include using namespace std; #define maxn 2000 #define maxt 10 #define MEM(a,b) memset(a,(b),sizeof(a)) #define MAX(a,b) ((a) > (b) ? (a) : (b)) #define MIN(a,b) ((a) < (b) ? (a) : (b)) #define MP make_pair #define pb push_back struct cycle { int x,sz; cycle() {x=sz=0;} cycle(int _sz,int _x) {sz=_sz; x=_x; } bool operator<(const cycle &c ) const{ return sz>c.sz; } }; int A[maxn+1],B[maxn+1]; int posA[maxn+1],posB[maxn+1]; int seen[maxn+1]; int ans[maxn+1]; int dp[2005][2005]; // dp[i][j]= maximum nodes u can take by breaking a cycle of length n to paths of lengths j+1 or j+2 int main() { int i,j,k,tests,n; for(i=2;i<=2000;i++) for(j=1;j<=i;j++) { if(i-j-1>=0 && j+dp[i-j-1][j] > dp[i][j]) // try a path of length j+1, contributing j to answer dp[i][j] = j+dp[i-j-1][j]; if(i-j-2>=0 && j+1+dp[i-j-2][j] > dp[i][j]) // try a path of length j+2, contributing j+1 to answer dp[i][j] = j+1+dp[i-j-2][j]; } scanf("%d",&tests); while(tests--) { scanf("%d",&n); assert(n>=1 && n<=maxn); MEM(posA,-1);MEM(posB,-1); for(i=0;i=1 && A[i]<=n && posA[A[i]]==-1); posA[A[i]]=i; } for(i=0;i=1 && B[i]<=n && posB[B[i]]==-1); posB[B[i]]=i; } vector cycles; MEM(seen,0); int maxLen=0; for(i=0;imaxLen) maxLen=tot; } printf("%d\n",maxLen); } return 0; }