+ محدودیت زمانی: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بعد از گردوندن مهدی ایزیُف در سطح دانشگاه PAP متوجه میشه که بر اثر کشیده شدن کله ی مهدی روی سطح زمین خطوطی بین دانشکده ها کشیده شدن.PAP میخواد که تعداد این خطوط رو بشمره تا خفن بودنش رو به همگان آشنا تر کنه (PAP از بیماری خود خفن بینی رنج می بره) اما از اونجایی که باید حواسش به مهدی و اسب ها باشه که در نرن این کار رو به محمدرضا می سپره. ولی محمدرضا که شمردن بلد نیست! اون از همه ی اعداد هم فقط اعداد 0 و 1 رو بلده روی یه سری خط ها عدد 0 و روی یه سری دیگه شون عدد 1 نوشته! اما ازونجایی که محمدرضا مدت خیلی طولانی ای از عمر پوچش رو (تقریبا 12سال) به خوندن یک صفحه از یک کتاب راجع به درخت ها بوده(حتی در تمام دوران تحصیلش و سر تمامی کلاس های دوران قبل دانشگاه،همیشه یه مداد سبز و یه مداد قهوه ای همراهش بود و درخت میکشید)، بعد از کلی کلنجار رفتن با خودش متوجه میشه که این دانشگاه ها و خطوط رسم شده بشدت شبیه به درختن (در نظریه گراف ها البته) و فورا این موضوع رو به اطلاع PAP میرسونه.PAP برای راستی آزمایی حرف محمدرضا و بخاطر اعتماد فوق العاده بالاش به محمدرضا خودش وارد عمل میشه و وقتی میبینه که محمدرضا به طرز عجیبی درست خبر داده، برای اینکه بخاطر شمارش افتضاحش تو ذوقش نزنه(به عنوان تشویق)،تصمیم میگیره که یه بازی براش طراحی کنه که از باقی عمرش لذت ببره.فورا دستورالعمل بازی رو براش توضیح میده: دو نوع دستور وجود داره که PAP میده هر مرحله: 1. اینکه $2$ راس از درخت انتخاب میکنه و به محمدرضا میگه عدد روی تمام یال های مسیر بینشونو از $0$ به $1$ و از $1$ به $0$ تغییر بده. 2. اینکه $2$ راس از درخت انتخاب میکنه و از محمد رضا میخواد مجموع عدد نوشته شده روی یال هاشو بنویسه. اما ازونجایی که محمدرضا تاحالا تو زندگیش هیچی جز درخت ندیده اصلا نمیفهمه که PAP چی میگه! برای همین میخواد که شما با زدن کد این بازی بهش بازیو یاد بدین. # ورودی در خط اول دو عدد $n$ و $q$ تعداد رئوس درخت و تعداد دستورات PAP n, q<=10^5 در $n - 1$ خط بعدی سه عدد $u$ و $v$ و $t$ که نشان دهنده یالی بین $u$ و $v$ با عدد اولیه $t$ است ( $t$ یا $0$ است یا $1$) در $q$ خط بعدی سه عدد $k$ و $u$ و $v$ که اگر $t = 1$ بود یعنی PAP دستور از نوع $1$ برای رئوس $u$ و $v$ داده است و اگر $t = 2$ بود یعنی PAP دستور از نوع $2$ برای رئوس $v$ و $u$ داده است # خروجی به ازای هر دستور از نوع $2$ باید عددی که دستور میخواهد را چاپ کنید # مثال ## ورودی نمونه 4 3 1 2 0 1 3 1 3 4 1 2 1 4 1 2 3 2 1 4 ## خروجی نمونه 2 1 ## توضیح ابتدا در مسیر بین $1$ و $4$ دو یال $1$ وجود دارد پس $2$ چاپ میکند سپس عدد یال های بین $2$ و $3$ تغییر میکنند (یعنی یال بین $1$ و $3$ برابر $0$ میشود و یال بین $1$ و $2$ برابر $1$ میشود) اکنون در مسیر بین $1$ و $4$ تنها یک یال $1$ وجود دارد (یال بین 3 و 4) پس 1 چاپ میکند