/* "بِسْمِ اللهِ الرَّحْمٰنِ الرَّحِيْمِ " -In the name of Allah." -------------------- A R I F ----------------------- */ #include // for order set --------------------- #include #include using namespace __gnu_pbds; #define ordered_set tree, rb_tree_tag, tree_order_statistics_node_update> #define index_of(x) find_by_order(x) // index_of the value x #define number_of(x) order_of_key(x) // how many value are stricly less then x // ------------------------------------ #define int long long int #define INF 1e18 #define PI 3.141592653 #define PB push_back #define F first #define S second #define MP(x, y) push_back(make_pair(x, y)) #define srt(v) sort(v.begin(), v.end()) #define all(x) x.begin(), x.end() #define rsrt(v) reverse(v.begin(), v.end()) #define no cout << "NO" << endl #define yes cout << "YES" << "\n" #define e "\n" #define pair vector< pair > #define deb(args...){string _s = #args;replace(_s.begin(), _s.end(), ',', ' ');stringstream _ss(_s);istream_iterator _it(_ss);err(_it, args);} using namespace std; template ostream &operator;<<(ostream &os;, const vector &v){ os << '{'; for (const auto &x : v) os << " " << x; return os << '}';} void err(istream_iterator it) {} template void err(istream_iterator it, T a, Args... args){ cerr << *it <<" = " << a << endl; err(++it, args...);} /*----------------------------------------------------------------------------------------*/ int expo(int a, int b, int mod) {int res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;} int mod_add(int a, int b, int m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;} int mod_mul(int a, int b, int m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;} int mod_sub(int a, int b, int m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;} int mminvprime(int a, int b) {return expo(a, b - 2, b);} int mod_div(int a, int b, int m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;} //only for prime m mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int getRandomNumber(int l, int r) {return uniform_int_distribution(l, r)(rng);} bool isBitSet(int num, int bitPosition) { return (num & (1 << bitPosition)) > 0 ; } /*----------------------------------------------------------------------------------------*/ //---------DFS---------------------------------------------------------------- const int mx = 1e6+7 ; vector g[mx] ; int vis[mx] = {0} ; int arr[mx] = {0} ; void graph(int u , int v ) { g[u].PB(v) ; g[v].PB(u) ; } int k , final = 0 ; void dfs(int node , int par) { vis[node] = 1 ; if(g[node].size() == 1){ arr[node] = 1 ; } for(auto it : g[node]) if(!vis[it]) dfs(it , node) ; std::map mp; if(g[node].size() != 1){ for(auto it : g[node]){ mp[arr[it]]++; } if(par != -1 and g[par].size() == 1) mp[1]++; for(int i =1 ; i<= k ; i++){ if(!mp[i]){ arr[node] = i ; break ; } } } } void dfs2(int node , int value) { vis[node] = 1 ; if(value == 1){ arr[node] = 2 ; }else arr[node] = 1 ; for(auto it : g[node]) if(!vis[it]) dfs2(it , arr[node]) ; } void dfs3(int node , int value) { vis[node] = 1 ; if(value == 1){ arr[node] = 2 ; }else if(value == 1 and g[node].size() != 1){ arr[node] = 3 ; } else arr[node] = 1 ; for(auto it : g[node]) if(!vis[it]) dfs3(it , arr[node]) ; } void Clear(int n) { for(int i =0 ; i<=n ; i++) { vis[i] =0 ; arr[i] = 0 ; final = 0 ; } } int ok(int n ) { std::map mp; for(int i =1 ; i<=n ; i++){ mp[arr[i]]++ ; } int ind = 1 ; std::vector v; for(auto it : mp){ v.PB(it.S) ; } srt(v) ; rsrt(v) ; int ans = 0 ; for(auto it : v){ ans += (it*ind); ind++ ; } return ans ; } //---------DFS---------------------------------------------------------------- void solve() { int n = 0 , m = 0 , ans = 0 , cnt = 0 ; cin >> n >> k ; for(int i =0 ; i> u >> v ; graph(u , v) ; } if(n == 1){ cout << 1 << e ; return ; } if(k == 1){ cout << -1 << e ; return ; } if(k>2){ for(int i =1 ; i<= n ; i++) if(!vis[i]) dfs(i, -1) ; ans = ok(n) ; Clear(n) ; for(int i= 1; i<=n ; i++) if(!vis[i]) dfs2(i , 0) ; ans = min(ans , ok(n)) ; Clear(n) ; for(int i= 1; i<=n ; i++) if(!vis[i]) dfs3(i , 0) ; ans = min(ans , ok(n)) ; } else{ for(int i= 1; i<=n ; i++) if(!vis[i]) dfs2(i , 0) ; ans = ok(n) ; } cout << ans << e ; } int32_t main() { ios_base::sync_with_stdio(false);cin.tie(NULL); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int test_case =1; // cin >> test_case ; int c = 0 ; while( test_case --) { // c ++ ; cout << "Case " << c << ": " ; solve() ; } } //vector::iterator lower, upper; //lower = lower_bound(v.begin(), v.end(), value) - v.begin() ; //upper = upper_bound(v.begin(), v.end(), value) - v.begin() ; --> // scanf("%s%d",s,&x) != EOF