[Solved] The Kingdom Division CodeCrush by NewtonSchool

This Valentine, Olivia is visiting the kingdom of Berland. Being the King of Berland, John wants Olivia to enjoy the setting before he asks her to marry him.

The kingdom consists of N cities and M roads. The I_th road connects cities U_i and V_i bidirectionally. It is guaranteed that for any pair of cities, at most one road exists between them. The kingdom is connected, and it is possible to reach any city from any starting city.

The capital of Berland is located in City 1. John wants to divide the kingdom into exactly two regions: the capital region (region containing the capital) and the commoners’ region. As commoners may find the capital region attractive, a security post must be installed on every road connecting the capital region and the commoners’ region to avoid migration. As John is running out of time, he can install at most K such security posts.

Since maintaining the capital region may cost a fortune, John wants the capital region to contain as few cities as possible. Also, both regions should be connected. Formally, it should be possible to reach any city in the capital region starting from any city in the capital region, without entering the commoners’ region. Similarly, it should be possible to reach any city in the commoners’ region starting from any city in the commoners’ region, without entering the capital region.

Your task is to help John find the smallest number of cities that the capital region can contain.

Input

The first line consists of three integers N (2 ≤ N ≤ 500), M (N – 1 ≤ M ≤ N * (N – 1) / 2), and K (0 ≤ K ≤ N).

The next M lines consists of two integers U_i and V_i . (1 ≤ U_i , V_i ≤ N, U_i ≠ V_i ).

Output

Print the smallest number of cities that the capital region can contain. If it is not possible to divide the kingdom, print -1.

Example

Sample Input 1:
6 8 2
1 2
1 3
1 4
2 3
3 4
2 5
4 6
5 6

Sample Output 1:
4

Explanation: The optimal strategy is to install security posts on roads (2, 5) and (4, 6). The capital region consists of {1, 2, 3, 4}.

Sample Input 2:
4 5 2
1 2
1 3
1 4
2 4
3 4

Sample Output 2:
3

Sample Input 3:
4 5 1
1 2
1 3
1 4
2 4
3 4

Sample Output 3:
-1

Solution

#include "bits/stdc++.h"
#ifdef mlocal
#include "./Competitive-Code-Library/snippets/prettyprint.h"
#endif
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
#define endl '\n'


int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, k; cin >> n >> m >> k;
	vector<vi> adj(n);
	for_(i, 0, m) {
		int a, b; cin >> a >> b;
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	set<ii> s; // good neigh, node
	vi good(n);
	for (auto i: adj[0]) good[i]++;
	
	for_(i, 1, n) s.insert({good[i], i});
	
	int curr = adj[0].size(), done_ct = 1;
	vector<bool> done(n);
	done[0] = true;
	
	while (curr > k) {
		ii pp = *s.rbegin(); s.erase(prev(s.end()));
		
		int p = pp[1], g = pp[0];
//		cout << "picking " << p + 1 << endl;
		curr += adj[p].size() - 2 * g;
		done[p] = true;
		done_ct++;
		
		for (auto i: adj[p]) {
			if (!done[i]) {
				s.erase({good[i], i});
				good[i]++;
				s.insert({good[i], i});
			}
		}
	}
	
	cout << (done_ct == n ? -1 : done_ct) << endl;
}

Happy Learning – If you require any further information, feel free to contact me.