The "FunFineFarm" game on a Facebook-like website called Ttcpcbook permits its player steal vegetables form others’ farm. It is a fun game but it made a serious headache to the honest Godgunman and therefore, he wants to know about his friends’ activities on this game.
The most different part between Ttcpcbook and Facebook is, there are two types of friends – "Direct" friends and "Indirect" friends. For any pair of users A and B, they are "Indirect" friends if and only if there is a unique sequence starts from A and ends at B such that every adjacent user pair in the sequence is a pair of "Direct" friends. Since this sequence is unique, we can also define a distance between A and B to be its length minus one. For example, suppose A-C-D-B is such a sequence that every adjacent pairs (i.e. A-C, C-D, D-B) is a pair of "Direct" friends. So the distance between A and B is 3 in this case. Note that a pair of "Direct" friends is also a pair of "Indirect" friends with length 1.
As a CSIE student, Godgunman hacked into Ttcpcbook, and, after tracing more than 2147483647 lines of ambiguous codes, he overflowed… Finally he gets some inspiration from a little book fulfilled with sine and cosine functions. He makes a conclusion: if someone could steal vegetables from another’s farm, then they must be a pair of ‚Indirect‛ friends with distance no more than k.
Now, it’s your time to help Godgunman to find out how many (unordered) 'Indirect‛ friends in the 'FunFineFarm‛ such that they can both steal the other’s vegetables?
There are multiple test cases in the input file, terminated by EOF. For each test case, the first line contains two integers n and k (1 ≦ k ≦ n ≦ 20,000), indicating the number of Godgunman's friends (excluding himself) and the limit of stealing distance respectively. Then in each of the next n lines contains two integers A, B, indicating that A and B are a "Direct" friend pair. You may assume all the data in the input file is correct, and all friends are numbered from 0 to n, and Godgunman's id is 0.
For each test case, please output the number of unordered pairs mentioned above.
4 2 0 2 2 3 3 1 3 4 2 1 0 1 1 2
8 2
Migrated from old NTUJ.
ttcpc2009 problem 4
| No. | Testdata Range | Score |
|---|