- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
خواجه فرزان به تازگی به خزپارتی در شکرستان دعوت شده! او باید تیپی خز برای مهمانی بزند. به یک تیپ شامل «کلاه»، «تی‌شرت» و «شلوار» خز می‌گوییم اگر رنگ آن‌ها دوبه‌دو متفاوت باشد. به خواجه بگویید چند تیپ ممکن می‌تواند بزند.
ورودی
در سطر اول ورودی $n$ تعداد پوشاک خواجه می‌آید.
$$1 \le n \le 100 , 000$$
در سطر $i$ام از $n$ سطر بعد در هر سطر دو عدد می‌آید که اطلاعات یکی از پوشاک خواجه فرزان را مشخص می‌کند. عدد اول $t_i$ نوع را مشخص می‌کند (اعداد ۱ و ۲ و ۳ را به ترتیب برای کلاه و تی‌شرت و شلوار فرض کنید.) و عدد دوم $c_i$ رنگ لباس را مشخص می‌کند.
$$ 1 \le c_i \le n$$
خروجی
در تنها سطر خروجی تعداد تیپ‌های خز ممکن با توجه به کمد لباس خواجه فرزان را خروجی دهید.
زیرمسئله
| نمره | محدودیت |
|---|---|
| ۵۰ | $ 1 \le n \le 100 $ |
| ۵۰ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
6
1 1
2 2
2 3
2 2
2 3
3 1
خروجی نمونه ۱
0
در مثال اول در همه حالات کلاه و شلوار همرنگ هستند و هیچ تیپی خز به شمار نمی‌آید.
ورودی نمونه ۲
9
1 1
2 1
3 1
1 5
2 5
3 5
1 9
2 9
3 9
خروجی نمونه ۲
6
در مثال دوم از ۳ رنگ هر ۳ نوع را داریم. پس طبق اصل ضرب برای کلاه ۳ حالت و برای تی‌شرت ۲ حالت و برای شلوار ۱ حالت داریم و پاسخ حاصل ضرب آن‌ها یعنی ۶ است.
ارسال پاسخ برای این سؤال