Human civilisation now has its base on another planet called Geekland, all credit goes to Geeklon Gusk.
There are N communication towers numbered from 0 to N-1 on the whole planet which are connected by M wires, each wire connects two different towers, more formally ith wire connects connections[i][0] and connections[i][1] tower. All towers run on 9G technology.
Geeklon Gusk has decided to upgrade the technology of some towers to 10G, the newest and fastest technology ever made. If tower a is upgraded to 10G, then all towers which are connected to tower a should also be upgraded. More formally two towers should have same technology if they are connected.
Geeklon only has enough budget to upgrade atmost X towers. Find maximum number of towers which can be upgraded.
Input:
N = 4, M = 2, X = 3
connections[][] = {{1, 2},
{0, 3}}
Output:
2
Explanation:
Either tower 1 and 2 or tower 3 and 4
can be upgraded.
Input:
N = 4, M = 3, X = 3
connections[][] = {{0, 1},
{1, 2},
{2, 3}}
Output:
0
Explanation:
No tower can be upgraded.