A. Баатрууд

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

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

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

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

2012 он ирж байна.

Эртний хорадрик домогт зааснаар энэ 2012 онд Диабло болон түүний дүү Мемфисто, Баал нар тамаас оргож хүн төрөлхтнийг заналхийлнэ хэмээжээ. Гэвч Арреат уулын оройд долоон зоригт баатрууд маань аймшигт мангасаас аврах гэж цугларсан байв.

Долоон эрэхлэг баатрууд нь : амазон $Anka$, зэрлэг $Chapay$, шулам $Cleo$, хувирагч $Troll$, ид шидтэн $Dracul$, хүлэг баатар $Snowy$ ба мэргэжлийн хит охин $Hexadecimal$. Баатрууд гурван мегабоссудыг устгахад хэр их туршлага авахыг мэдэж байгаа : $a$ нь Mephisto, $b$ нь Diablo, $c$ нь Baal.

Таны даалгаравар бол : баатрууд долуулаа, мегабоссууд гурвуулаа! Энгээд баатрууд гурван багт хуваагдаж багаараа мегабоссуудыг устгахаар болов. Багийн гишүүн бүр тоог доош тоймлосонтой тэнцүү туршлагыг олж авна. $x$ нь устгасан мегабоссоос авах туршлага, $y$ нь багт байгаа гишүүдийн тоо.

Баатрууд бие биенийхээ сэтгэлийг өвтгөмөөргүй байгаа. Тийм учраас хамгийн их туршлагатай баатар болон хамгийн бага туршлагатай баатруудын туршлагын зөрүүг хамгийн бага байхаар хуваагдахыг хүсч байгаа. Нэгэнтээ багуудад хуваагдсан юм чинь та тэдний багуудад байгаа таалагдалтын тоо хамгийн их байхаар олох болжээ.

Зарим баатарт зарим баатрууд таалагддаг. Гэхдээ $p$ баатарт $q$ баатар таалагддаг гэлээ гээд $q$ баатарт $p$ баатар таалагддаг гэсэн үг биш. Аль ч баатар өөрөө өөртөө таалагддаггүй.

Хуваарилсан багт байгаа баатруудын таалагдалтыг олохдоо багт $p$ болон $q$ баатрууд нэг багт байдаг бөгөөд $p$ баатарт $q$ баатар таалагддаг байх бүх хослолыг тоолох юм. Хэрэв $p$ болон $q$ бие биендээ таалагддаг бөгөөд нэг багт байвал хоёр удаа тоологдох юм.

Баг ганцхан баатраас бүтэж болно, хамгийн чухал нь мегабоссууд устах явдал юм. Бүх баатрууд мангасуудтай тулалддаг. Нэг баатар нэгээс олон багт байж болохгүй.

Баатрууд ганцаараа байсан ч мегабоссыг устгаж чаддаг.

Оролт

Эхний мөрөнд $n$ ($0 ≤ n ≤ 42$) бүхэл тоо - баатруудын дунд байх таалагдалтыг мэдээлэл. Дараагийн $n$ мөр "$p likes q$" хэлбэртэйгээр $p$ баатарт $q$ баатар (p$ $ ≠ $ q$) таалагддагийг илэрхийлнэ. Таалагдалтын мэдээлэл бүгд ялгаатай байна. Аль ч баатар өөрөө өөртөө таалагддаггүй.

Сүүлийн мөрөнд $a$, $b$, $c$ ($1 ≤ a, b, c ≤ 2*10^{9}$) бүхэл тоонууд : харгалзан Mephisto, Diablo, Baal нарыг устгахад өгөх туршлага.

Өгүүлбэр дээрх өгөгдлөөс бусад бүх өмнөх-тестүүдэд $a = b = c$ нөхцлийг хангадаг байна.

Гаралт

Хариу болох хоёр тоо - хамгийн бага хамгийн их туршлагатай баатар болон хамгийн бага туршлагатай баатруудын туршлагын зөрүү, таалагдалтын тоо.

Хариуны хоёрдугаар тоог тооцоолохдоо хамгийн эхлээд эхний тоог хамгийн их болгоод, хамгийн их байх багуудын хуваалтууд дундаас хамгийн их таалагдалттайг сонгоно.

Орчуулсан: Б.Алтангэрэл

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

Оролт
3
Troll likes Dracul
Dracul likes Anka
Snowy likes Hexadecimal
210 200 180
Гаралт
30 3
Оролт
2
Anka likes Chapay
Chapay likes Anka
10000 50 50
Гаралт
1950 2

Тэмдэглэл

Эхний жишээнд эхний багийг $Dracul$, $Troll$ болон $Anka$, хоёрдугаар багийг $Hexadecimal$ болон $Snowy$, гуравдугаар багийг $Cleo$ ба $Chapay$ гэж хуваарилана.

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