3200 سال پیش کشور مصر از $n$ قلمرو تشکیل شده‌ بود. میان برخی از قلمرو‌ها جاده‌های دوطرفه وجود دارد که با استفاده از این جاده‌ها می‌توان از هر قلمرو به هر قلمرو دیگری رسید.

رامسس دوم که یکی از فرعون‌های مصر باستان است، تصمیم گرفته که سرزمین خود را میان دو فرزندش تقسیم کند اما از بخت بدش این دو برادر کینه‌توز و ناخلف هستند. پس پادشاه تصمیم گرفت که یک بازی طراحی کند تا بتواند سرزمین را بین دو برادر به گونه‌ای تقسیم کند که از جنگ و دعوا میان آن دو پیشگیری کند.

بدین منظور در ابتدا یک قلمرو را به عنوان پایتخت برای پسر بزرگش انتخاب می‌کند تا کاخ فرمانروایی پسر ارشد در آنجا ساخته شود و بعد از آن قلمرو دیگری برای پایتخت پسر دومش انتخاب خواهد کرد. سپس دو برادر باید به نوبت یک بازی را انجام بدهند. در مرحله‌ی اول برادر بزرگتر هر تعداد از جاده‌های متصل به پایتختش را به دلخواه از بین می‌برد. حال نوبت برادر کوچکتر می‌شود و او نیز باید به دلخواه تعدادی از جاده‌هایی که به پایتختش متصل‌اند را از بین ببرد، ولی باید به گونه‌ای این کار را انجام دهد که دیگر هیچ مسیری بین پایتخت خودش و پایتخت برادر بزرگترش وجود نداشته باشد. دقت کنید که هیچ کدام لزوما مجبور به از بین بردن جاده‌ای نیستند و می‌توانند هیچ جاده‌ای را از بین نبرند؛‌ تنها قانون بازی این است که برادر کوچکتر به گونه‌ای حرکتش را انجام دهد که دیگر مسیری بین پایتختش و پایتخت برادرش وجود نداشته باشد.

بعد از این بازی دو مرحله‌ای، هر برادر بر کل قلمرو‌هایی که در مولفه‌ی همبندی پایتختشان قرار دارد حکمرانی خواهد کرد (اگر یک قلمرو در هیچکدام از این دو مولفه‌ی همبندی نباشد مستقل خواهد شد!). هر برادر به گونه ای بازی می‌کند که تعداد قلمروهای حکومتش منهای تعداد قلمروهای حکومت برادرش ماکسیمم شود.

رامسس دوم به دنبال این است که بین تمامی $n(n - 1)$ حالت انتخاب پایتخت برای دو پسرش، جمع تعداد قلمرو های حکومت پسر بزرگترش را محاسبه کند. همچنین او در جهت توسعه کشورش، هر سال یک جاده به جاده‌های مصر باستان اضافه می‌کند (ممکن است این جاده قبلا وجود داشته باشد یا حتی بین دو قلمرو یکسان باشد). شما باید به او کمک کنید تا جواب سوال را علاوه بر امسال، برای هر یک از $q$ سال آینده هم حساب کند.

در خط اول دو عدد $n$،‌ تعداد قلمروها و $m$، تعداد جاده‌های اولیه مصر باستان می‌آید.

در $m$ خط بعدی در هر خط دو عدد $u$ و $v$ می‌آید که به معنی یک جاده دو طرفه میان این دو قلمرو است.

در خط بعدی عدد $q$ یعنی تعداد سال‌ها می‌آید.

در $q$ خط بعدی در هر خط دو عدد $u$ و $v$ می‌آید که به معنی اضافه شدن یک جاده دو طرفه میان این دو قلمرو است.

تضمین می‌شود که گراف ورودی مصر باستان در ابتدا ساده و همبند است.(ممکن است بعد از تعدادی کوئری دیگر ساده نباشد.)

در $q + 1$ خط خروجی (به ازای گراف اولیه مصر باستان و بعد از گذشت هر سال) جواب مسئله را خروجی دهید.

• زیرمسئله اول (۸ نمره): گراف ابتدایی مصر باستان به شکل درخت است، $q = 0$.
• زیرمسئله دوم (۱۷ نمره): $q = 0$
• زیرمسئله سوم (۱۵ نمره): گراف ابتدایی مصر باستان به شکل مسیر است.
• زیرمسئله چهارم (۲۷ نمره): قطر گراف ابتدایی مصر باستان حداکثر $100$ است.
• زیرمسئله پنجم (۴۰ نمره): $n, m, q \le 2 \times 10^5$.
• زیرمسئله ششم (۴۰ نمره): بدون محدودیت اضافی.

• $1 \leq n \leq 3 \times 10^5$
• $n - 1 \leq m \leq 3 \times 10^5$
• $0 \leq q \leq 3 \times 10^5$
• $1 \leq u, v \leq n$

3 2
1 2
2 3
2
1 3
2 2

10
12
12

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

702
718
738

در ورودی نمونه اول، قبل از اضافه شدن جاده، اگر پایتخت برادر بزرگتر قلمرو $1$ باشد و پایتخت برادر کوچکتر قلمرو $3$ باشد، برادر بزرگتر جاده‌ای از بین نمی‌برد و برادر کوچکتر مجبور است تنها جاده‌ی متصل به $3$ را از بین ببرد. بنابراین برادر بزرگتر بر قلمرو $1$ و $2$ حکومت خواهد کرد، و برادر کوچکتر بر قلمرو $3$. که تعداد قلمرو های برادر بزرگتر $2$ تا می‌شود. اگر این مقدار را برای هر $3 \times (3 - 1) = 6$ حالت ممکن جمع بزنیم، به مقدار $10$ می‌رسیم.