+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- "Let go your earthly tether. Enter the void. Empty and become wind" گورو لاقیما، راهب باستانی، اسرار بسیار زیادی با خود دفن کرده‌است. اخیرا باستان‌شناسان کتیبه‌ای کهنه متعلق به گورو پیدا کرده‌اند که روی آن تکه‌کد زیر نوشته شده‌است. move() next_node <- adj[current][pointer[current]] pointer[current] <- (pointer[current] + 1) % adj[current].size() current <- next_node cost++ seen[current] <- true move() باستان شناسان معتقدند این تکه کد، راز حرکت ستارگان و سرّ پشت طالع آدم‌ها را فاش خواهد کرد. در ادامه این کتیبه گفته‌شده است که adj بیانگر لیست مجاورت راس‌های یک درخت است و در ابتدا شرایط زیر برقرار است: + مقدار همه‌ی خانه‌های آرایه pointer برابر $0$ است. + مقدار current برابر $0$ است. + مقدار cost برابر $0$ است. + مقدار همه خانه‌های آرایه seen به‌جز خانه‌ی $0$ برابر false است و مقدار $seen[0]$ برابر با true است. پس از مدتی تحقیق، باستان‌شناسان به این نتیجه رسیدند که این روش حرکت روح گورو لاقیما بر روی یک درخت بوده و در واقع current مکان او در هر لحظه را نشان می‌دهد. بدیهی است که او تا ابد روی این درخت حرکت خواهد کرد. برای کشف راز حرکت ستارگان، باستان‌شناسان باید مقدار cost را در اولین لحظه‌ای که گورو لاقیما همه‌ی رئوس درخت را می‌بیند (همه‌ی خانه‌های آرایه seen برابر با true می‌شود) بدست آورند. توجه کنید که دانشمندان کامپیوتر توانسته‌اند ثابت کنند که چنین لحظه‌ای به ازای هر درخت و هر ترتیبی از لیست‌های مجاورت حتما وجود خواهد داشت. # ورودی در سطر اول ورودی عدد $n$ آمده‌است. در $i$ امین سطر (با شروع از صفر) از $n$ سطر بعدی ابتدا عدد $k$ آمده‌است؛ سپس $k$ عدد آمده‌است که لیست همسایه‌های راس $i$ یعنی اعداد $ adj[i]$ را نشان می‌دهد. $$1 \le n \le 300\ 000$$ $$0 \le adj_{i,j} < n$$ گراف داده‌شده درخت است. اگر یالی بین دو راس $v$ و $u$ باشد. تضمین می‌شود $u$ در لیست همسایگان $v$ ظاهر می‌شود و برعکس. # خروجی در تنها سطر خروجی، مقدار خواسته‌شده را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱ | ۶ | $n \le 300$| |۲| ۱۱ | درجه همه رئوس درخت حداکثر $2$ است و درجه راس $0$ حداکثر $1$ است. | |۳| ۲۸ |درجه همه رئوس حداکثر $2$ است. | |۴| ۵۵ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 7 3 1 2 3 1 0 4 5 6 0 4 1 0 1 2 1 2 1 2 ``` ## خروجی نمونه ۱ ``` 14 ```

حل سؤال در بانک سؤالات