FOXLINGS  Foxlings
It’s Christmas time in the forest, and both the Fox and the Wolf families are celebrating. The rather large Fox family consists of two parents as well as $N$ ($1 \leq N \leq 10^9$) little Foxlings. The parents have decided to give their children a special treat this year – crackers! After all, it’s a wellknown fact that Foxen love crackers.
With such a big family, the parents can’t afford that many crackers. As such, they wish to minimize how many they give out, but still insure that each Foxling gets at least a bit. The parents can only give out entire crackers, which can then be divided and passed around.
With this many children, not all of them know one another all that well. The Foxlings have names, of course, but their parents are computer scientists, so they have also conveniently numbered them from $1$ to $N$. There are $M$ ($1 \leq M \leq 10^5$) unique twoway friendships among the Foxlings, where relationship $i$ is described by the distinct integers $A_i$ and $B_i$ ($1 \leq A_i,B_i \leq N$), indicating that Foxling $A_i$ is friends with Foxling $B_i$, and vice versa. When a Foxling is given a cracker, he can use his tail to precisely split it into as many pieces as he wants (the tails of Foxen have many fascinating uses). He can then pass these pieces around to his friends, who can repeat this process themselves.
Input
Line $1$: 2 integers, $N$ and $M$
Next $M$ lines: 2 integers, $A_i$ and $B_i$, for $i=1..M$
Output
A single integer – the minimum number crackers must be given out, such that each Foxling ends up with at least a small part of a cracker.
Example
Input:
9 5 3 1 6 1 7 6 2 7 8 9
Output:
4
Explanation of Sample:
The parents can give one cracker to Foxling 6, who will then split it into three and give pieces to his friends (Foxlings 1 and 7). Foxling 7 can then give half of his piece to his other friend, Foxling 2.
They can give another cracker to Foxling 8, who will split it with Foxling 9.
This leaves Foxlings 4 and 5, who have no friends (don’t worry, Foxen have long since outgrown the need for friends), and who must be given one cracker each. This brings the total up to 4 crackers.
hide comments
sherlock11:
20180615 07:06:12
constraint for n is 10^9 not 10^5........costed me hell lot of time and TLEs............. 

anirudnits:
20180515 21:42:15
got 2 WA's and then an AC on the very same code!!! 

nadstratosfer:
20171019 04:49:58
My DSU in Python TLE'd, got AC with another approach. Is it too much to ask that the time limit be set so that the expected algorithm can pass? With the input appearing to be megabytes in size, many people will fail on IO alone, never knowing how good or bad their actual solution was. 

rupeshyadav:
20170919 14:05:39
Hi @Siddharth Singh, how did you asked for help, i don't see any way of contacting people? please let me know if i am missing something.


ayush926:
20170909 10:26:50
AC. DSU and map :) 

pvsmpraveen:
20170228 16:45:54
AC bitset ;) 

ganeshjadhav:
20170125 10:41:27
binary search and disjoint set AC in 1 go. 

shreeyash:
20170124 06:03:11
TL is very strict 

Mayank Agarwal:
20161222 09:05:57
can be done without DSU!! 

yash_18:
20160825 14:35:46
maps :D 
Added by:  SourSpinach 
Date:  20130507 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 