The Space WAR
All submissions for this problem are available.There is an all-out war going on in space and as we all know intel is important. You have a network of spies and you have gathered some valuable intel and want to send it to your soldiers as soon as possible, there are $N$ soldiers under your command. Some soldiers are in contact with each other and some are not. If a soldier has some information he/she will forward it to his neighbors in $1$ unit time. Now there is a restriction in place for you, you can only tell $1$ soldier in each of these connected groups of soldiers. You have to now select these points of contact in such a way that the total time taken for the intel to spread among the soldiers is minimum possible. There are $M$ distinct pairs of soldiers in contact with each other. There are no cycles in the graph. ###Input: - Each testcase contains two integers $N, M$. - M lines follow containing two integers $U$ and $V$ such that $U$ and $V$ share information with each other. ###Output: For each testcase, output the minimum time for spreading the information. ###Constraints - $1 \leq N \leq 10^5$ - $0 \leq M \leq 10^5$ - $1 \leq U, V\leq N$ ###Sample Input: 3 2 1 2 2 3 ###Sample Output: 1 ###EXPLANATION:
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.