نقاشی بچه‌ی آقا داوود

بچه‌ی آقا داوود می‌خواهد با مداد رنگی‌های جدیدش یک درخت بزرگ بکشد! درخت مورد نظر $N$ رأس دارد و رأس‌هایش از $1$ تا $N$ شماره‌گذاری شده‌اند. بچه‌ی آقا داوود در ابتدا رأسی از درخت را می‌کشد. سپس در هر مرحله یک رأس جدید را با یالش به درخت اضافه می‌کند. او می‌خواهد تمام رأس‌های درخت را رسم کند به طوری که در حین کشیدن نقاشی همواره درخت همبند باشد. آقا داوود که از کار بچه‌اش تعجب کرده است می‌خواهد بداند که بچه‌اش به چند طریق می‌تواند این درخت را بکشد. به آقا داوود کمک کنید.

• سطر اول ورودی شامل یک عدد طبیعی، $1 \leq N \leq 10^5$، تعداد رأس‌های درخت، است.
• سطر‌های دوم تا $N$-ام ورودی هر کدام شامل دو عدد طبیعی هستند که دو سر یک یال از درخت هستند.
• تضمین می‌شود ورودی یک درخت $N$ رأسی می‌باشد.
• در ۳۰ درصد از ورودی‌ها، $1 \leq N \leq 2000$، است.

در تنها سطر خروجی جواب را به پیمانه‌ی $7+10^9$ چاپ کنید.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت

• سوال بعد
• سوال قبل