#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include //#include //#include //#include //#include //#include //#include //#include //#include //#if __cplusplus >= 201103L //#include //#include //#include //#include // //#define cauto const auto& //#else //#endif using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; typedef vector vint; typedef vector > vvint; typedef vector vll, vLL; typedef vector > vvll, vvLL; #define VV(T) vector > template void initvv(vector > &v, int a, int b, const T &t = T()){ v.assign(a, vector(b, t)); } template void convert(const F &f, T &t){ stringstream ss; ss << f; ss >> t; } #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define reep(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) reep((i),0,(n)) #define ALL(v) (v).begin(),(v).end() #define PB push_back #define F first #define S second #define mkp make_pair #define RALL(v) (v).rbegin(),(v).rend() #define DEBUG #ifdef DEBUG #define dump(x) cout << #x << " = " << (x) << endl; #define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; #else #define dump(x) #define debug(x) #endif #define MOD 1000000007LL #define EPS 1e-8 #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL #define maxs(x,y) x=max(x,y) #define mins(x,y) x=min(x,y) /*********************************************************************/ class UF { public: static const int ufmax=100052; int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax]; UF() { init();} void init(){int i; rep(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } } int find(int x) { return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));} int operator[](int x) {return find(x);} int count(int x) {return ufcnt[find(x)];} void unite(int x,int y) { x = find(x); y = find(y); if(x==y) return; if(ufrank[x]>n>>m; UF uf; rep(i,m){ int a,b; cin>>a>>b; uf.unite(a-1,b-1); } vint v(n); rep(i,n){ v[uf[i]]++; } vint cnt(n); rep(i,n){ cnt[v[i]]++; } vint dp(n+1,INF); dp[0]=-1; reep(i,1,n+1){ if(cnt[i]==0) continue; for(int j=1;;j<<=1){ int t=min(cnt[i],j); for(int k=n-t*i;k>=0;k--){ mins(dp[k+t*i],dp[k]+t); } if(j>=cnt[i]) break; } } vint tmp={0,0,0,1,1,2}; if(n==6&&m==3){ rep(i,3){ assert(tmp[i]==dp[i+1]); } } rep(i,n){ if(dp[i+1]==INF) cout<<-1<