#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;// push_back inline int read(){ int sum=0,x=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') x=0; ch=getchar(); } while(ch>='0'&&ch<='9'){ sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar(); } return x?sum:-sum;}inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0');}int mi(int x,int y){ return x
            
             y?x:y;}const int M=1505;const int inf=0x3f3f3f3f;vector
             
              g[M];int dp[M][2],f[M];void dfs(int u){ dp[u][0]=0,dp[u][1]=1; for(int i=0;i