E. Нууцлаг сийлбэрүүд

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Цагаан баавгайнууд дээрээ хэд хэдэн нууцлаг сийлбэр агуулсан маш том хөвж буй дугуй мөс олсон. Мөсөн дээр $n$ шулуун сийлсэн байсан. Шулуун бүр мөсний хүрээн дээр байгаа хоёр цэгийг (эдгээр цэгүүдийг төгсгөлийн цэгүүд гэж нэрлэе) холбосон байсан.

Одоо 6 цагаан баавгайн баг буюу Алис, Боб, Кэрол, Дэйв, Эвэ, Фрэнк нар төгсгөлийн цэгүүд дээр урц барих гэж байна. Баавгай бүр урц барьж түүндээ амьдрахыг хүсч байна. Ямар ч хоёр цагаан баавгай нэг төгсгөлийн цэг дээр урц барьж чадахгүй. Алис Боб хоёр бол мухар сүсэгтэй хайртууд. Тэд шулуунуудыг харийнхан сийлсэн гэж итгэж байгаа ба тодорхой далдын хүчтэй гэж бодож байна. Кэрол болон Дэйв мөн Эвэ болон Фрэнк нар ч мөн адил ингэж бодож байна.

X ба Y хоёр урцны хоорондох зай нь X-с Y-рүү мөсний хүрээгээр явахад дайрч өнгөрөх урцуудын (урцуудын төгсгөлийн цэгүүдийг тоолохгүй) хамгийн бага тоон дээр нэгийг нэмсэнтэй тэнцүү байна.

Шударга байх үүднээс гурван хосуудын хоорондын зай тэнцүү байх ёстой (Алис ба Бобын хоорондох зай, Кэрол болон Дэйвийн хоорондох зай, Эвэ болон Фрэнкийн хоорондох зай).

Доорх зурагт хоёр ялгаатай тохиргоог үзүүлсэн ба тойрог дээрх цэгүүд нь төгсгөлийн цэгүүд юм. Зүүн талд байгаа тохиргоо нь хүчинтэй биш. Хосууд (A ба B, C ба D, E ба F) хоорондоо шулуунаар холбогдсон боловч зайн шаардлагыг хангахгүй байна. A болон B хоёрын хоорондох зай нь 2 (A-c B-рүү цагийн зүүний дагуу F-р дайран явж болно). E ба F хоёрын хоорондох зай ч мөн 2. Гэсэн ч C ба D хоёрын хоорондох зай 1 (C-c D-рүү цагийн зүүний эсрэг ямар ч урц дайран өнгөрөхгүйгээр явж болно) байна. Баруун талын тохиргоо хүчинтэй. Гурван хосын зай бүгд адилхан 1 байна.

Нөхцөлүүдийн дагуу урцуудыг барих замуудын тоог ол. Ашиглагдсан 6 төгсгөлийн цэгүүд нь ижил бол уг хоёр тохиргоо нь ижилд тооцогдоно.

Оролт

Эхний мөрөнд бүхэл тоо $n$($3 ≤ n ≤ 10^{5}$) байх буюу шулуунуудын тоо юм.

Дараагийн $n$ мөр бүрт хоёр бүхэл тоо $a_{i}, b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ 2n$) байх буюу мөсөн дээр $a_{i}$-р ба $b_{i}$-р төгсгөлийн цэгүүдийг холбосон шулуун сийлэгдсэн байна гэдгийг илэрхийлнэ.

Төгсгөлийн цэг бүр яг нэг шулуунтай холбогдсон байна.

Гаралт

Урцуудыг барих боломжийн тоог хэвлэ.

C++ хэлэнд 64 битийн бүхэл тонуудыг унших болон бичихдээ $\%lld$ тодорхойлогчийг битгий ашиглаарай. $cin$, $cout$ урсгалууд болон $\%I64d$ тодорхойлогчийг ашиглаарай.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
4
5 4
1 2
6 7
8 3
Гаралт
2
Оролт
8
1 7
2 4
3 9
5 11
6 8
10 16
13 15
14 12
Гаралт
6

Тэмдэглэл

Хоёр дахь жишээ бодлогын нөхцөл дахь зурагтай харгалзана.

Сэтгэгдлүүдийг ачааллаж байна...