prithivMLmods/Coder-Stat

1 2<H1><font color="#000000">Problem E:</font> Huge Family</H1>3 4<p>5Mr. Dango's family has extremely huge number of members. Once it had about 100 members, and now it has as many as population of a city. It is jokingly guessed that the member might fill this planet in near future. They all have warm and gracious personality and are close each other.6</p>7 8<p>9They usually communicate by a phone. Of course, They are all taking a family plan. This family plan is such a thing: when <i>a</i> choose <i>b</i>, and <i>b</i> choose <i>a</i> as a partner, a family plan can be applied between them and then the calling fee per unit time between them discounted to <i>f</i>(<i>a</i>, <i>b</i>), which is cheaper than a default fee. Each person can apply a family plan at most 2 times, but no same pair of persons can apply twice. Now, choosing their partner appropriately, all members of Mr. Dango's family applied twice.10</p>11<p>12Since there are huge number of people, it is very difficult to send a message to all family members by a phone call. Mr. Dang have decided to make a phone calling network that is named '<i>clan</i>' using the family plan. Let us present a definition of <i>clan</i>.13</p>14 15<p>16Let <i>S</i> be an any subset of all phone calls that family plan is applied. <i>Clan</i> is <i>S</i> such that:17<ol>18<li> For any two persons (let them be <i>i</i> and <i>j</i>), if <i>i</i> can send a message to <i>j</i> through phone calls that family plan is applied (directly or indirectly), then <i>i</i> can send a message to <i>j</i> through only phone calls in <i>S</i> (directly or indirectly).</li>19<li> Meets condition 1 and a sum of the calling fee per unit time in <i>S</i> is minimized.</li>20</ol>21</p>22 23<p>24<i>Clan</i> allows to send a message efficiently. For example, we suppose that one have sent a message through all calls related to him in the clan. Additionaly we suppose that every people follow a rule, "when he/she receives a message through a call in clan, he/she relays the message all other neibors in respect to clan." Then, we can prove that this message will surely be derivered to every people that is connected by all discounted calls, and that the message will never be derivered two or more times to same person.25</p>26 27<p>28By the way, you are given information about application of family plan of Mr. Dango's family. Please write a program that calculates that in how many ways a different clan can be constructed. You should output the answer modulo 10007 because it may be very big.29</p>30 31 32<H2>Input</H2>33 34<p>35The input consists of several datasets.36</p>37 38<p>39The first line of each dataset contains an integer <i>n</i>, which indicates the number of members in the family.40</p>41 42<p>43Next <i>n</i> lines represents information of the <i>i</i>-th member with four integers. The first two integers respectively represent <i>b</i>[0] (the partner of <i>i</i>) and f(<i>i</i>, <i>b</i>[0]) (the calling fee per unit time between <i>i</i> and <i>b</i>[0]). The following two integers represent <i>b</i>[1] and <i>f</i>(<i>i</i>, <i>b</i>[1]) in the same manner.44</p>45 46<p>47Input terminates with a dataset where n = 0.48</p>49 50<H2>Output</H2>51 52<p>53For each dataset, output the number of <i>clan</i> modulo 10007.54</p>55 56<H2>Constraints</H2>57 58<ul>59<li>3 &le; <i>n</i> &le; 100,000</li>60</ul>61 62<H2>Sample Input</H2>63<pre>643651 1 2 3660 1 2 2671 2 0 3687691 2 2 1700 2 3 2710 1 3 1722 1 1 2735 3 6 2744 3 6 1754 2 5 176077</pre>78 79<H2>Output for the Sample Input</H2>80<pre>81182283</pre>84 85