## 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 ≤ `N` ≤ 1,000,000,000) little foxlings. The parents have decided to
give their children a special treat this year - crackers! After all, it's a well-known
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 ensuring 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 ≤ `M` ≤ 100,000) unique two-way friendships among the foxlings, where
relationship `i` is described by the distinct integers `A _{i}`
and

`B`(1 ≤

_{i}`A`,

_{i}`B`≤

_{i}`N`), indicating that foxling

`A`is friends with foxling

_{i}`B`, 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.

_{i}
Line 1: Two integers - `N` and `M`

Next `M` lines: Two integers - `A _{i}` and

`B`

_{i}### Output

The minimum number of crackers that must be given out so that each fox ends up with at least a bit of a cracker.### Sample Input

9 5 3 1 6 1 7 6 2 7 8 9

### Sample Output

4

### Explanation

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.

All Submissions

Best Solutions

**Point Value:** 10 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Mar 11, 2009

**Author:** SourSpinach

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

sigkillon Nov 26, 2015 - 1:42:26 am UTC Erroneous DataCase #1 has m = 0

Cases #5 through #12 have A_i = B_i for some i

These violate the specification. See http://wcipeg.com/submissions/status/335913

Danielon May 03, 2009 - 4:32:31 pm UTC help?It seems that even compressing the nodes on the TLE cases causes it to TLE...

Edit 1: Seems that quicksort times out on the 13th test case...

Darn worst case of O(n^2)

Edit 2: Heap sort seems to work... Thanks for the help!

hansonw1on May 03, 2009 - 5:03:05 pm UTC Re: help?1. Your get() code takes log(M) time for the binary search, and on average M/2 time for the insertion. (The binary search is kinda useless, since you insert anyway) Since you'll eventually run get() for every vertex, this takes about M*M/2 steps.

2. In the find procedure, you go through all the edges for every vertex - this takes about M*M steps.

Overall, you can see that it takes some multiple of M*M time.

Since M <= 100,000, this is far too slow. A modern computer will only run approximately 20-50 million operations per second.

To compress the nodes in a smarter way, try reading all the nodes in, and then sorting them with something like quick/merge sort. (which takes N*log(N) time on average). Then you can find the indices pretty easily, with a binary search.

In the find() loop, you can use something similar. Unfortunately, Pascal doesn't have any library functions for this sort of thing, so you'll have to do a lot of extra coding.

The new algorithm should take roughly M*log(M) time, which is ~2 million - more than fast enough to run in time.

SourSpinachon Apr 20, 2009 - 2:09:56 am UTC HintHowever, N is far too large for this to run in time. The key observation is that with M edges, only up to 2M nodes can be connected to others, leaving many nodes with no neighbours (hence forming their own connect components).

platynumplatypuson Mar 11, 2009 - 9:17:49 pm UTC ummmmmSourSpinachon Mar 11, 2009 - 9:35:41 pm UTC Re: ummmmmKeep in mind that the first line of input is NOT a friendship, it's N and M.

platynumplatypuson Mar 11, 2009 - 10:18:49 pm UTC Re: Re: ummmmm