- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
خواجه فرزان به تازگی به خزپارتی در شکرستان دعوت شده! او باید تیپی خز برای مهمانی بزند. به یک تیپ شامل «کلاه»، «تیشرت» و «شلوار» خز میگوییم اگر رنگ آنها دوبهدو متفاوت باشد. به خواجه بگویید چند تیپ ممکن میتواند بزند.
ورودی
در سطر اول ورودی \(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
در مثال دوم از ۳ رنگ هر ۳ نوع را داریم. پس طبق اصل ضرب برای کلاه ۳ حالت و برای تیشرت ۲ حالت و برای شلوار ۱ حالت داریم و پاسخ حاصل ضرب آنها یعنی ۶ است.