G. Санал болгосон найзууд

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

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

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

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

Поликарфус нийгмийн сүлжээний програмистаар ажиллаж эхэлсэн. Түүний дарга санал болгосон найзуудыг тодорхойлох бүтцийг хөгжүүлэх даалгавар өгсөн. Поликарфус их бодсоны эцэст дараах дүгнэлтэд хүрсэн.

Нийгмийн сүлжээний бүх нөхөрлөлийн харилцаа $m$ хэрэглэгчийн нэр $a_{i}, b_{i}$ $(a_{i} ≠ b_{i})$ хосууд өгөгдсөн. $a_{i}, b_{i}$ хос бүр нь $a_{i}$ ба $b_{i}$ хэрэглэгчид найзууд гэсэн үг. Нөхөрлөлийн харилцаа тэгш эрхтэй, өөрөөр хэлбэл $a_{i}$ нь $b_{i}$-тэй найз бол $b_{i}$ нь $a_{i}$-тэй найз. Хэрвээ дараах нөхцлүүдийг хангаж байвал хэрэглэгч $y$ нь хэрэглэгч $x$-н санал болгосон найз :

  1. $x ≠ y$;
  2. $x$ ба $y$ найзууд биш;
  3. сүлжээний бүх хэрэглэгчид дундаас эхний хоёр нөхцлийг хангасан, хэрэглэгч $y$-ийн хувьд хэрэглэгч $x$ нь хамгийн их ерөнхий (дундын) найзтай байна, $y$, $x$ нь хоюулаа $z$ хэрэглэгчтэй найзууд бол $z$ нь $x$, $y$ $(z ≠ x, z ≠ y)$ хэрэглэгчдийн ерөнхий найз болно.

Таны даалгавар бол Поликарфусд санал болгосон найзуудыг тодорхойлох бүтцийг хэрэгжүүлэхэд нь туслах юм.

Оролт

Эхний мөр нь нийгмийн сүлжээний найзуудын хосын тоо $m$ $(1 ≤ m ≤ 5000)$ бүхэл тоог агуулна. Дараагийн $m$ мөрүүд нь найзуудын нэрнүүдийн хосыг агуулна. $i$-р мөр нь зайгаар тусгаарлагдсан $a_{i}$, $b_{i}$ $(a_{i} ≠ b_{i})$ нэрнүүдийг агуулна. Хэрэглэгчдийн нэрнүүд нь хоосон биш ба хамгийн ихдээ 20-н Англи дармал жижиг үсгээс бүрдэнэ.

Оролтод найзуудын хос бүр зөвхөн нэг удаа тохиолдоно. Жишээ нь оролт $x$, $y$ ба $y$, $x$-г зэрэг агуулж болохгүй. Ялгаатай хэрэглэгчдийн нэр ялгаатай байх нь баталгаатай болно. Нийгмийн сүлжээний хэрэглэгч бүр дор хаяж нэг найзтай байна. Сүүлийн зүйл нь хэрэглэгчийн нэр бүр наад зах нь нэг удаа тохиолддог байх нь баталгаатай юм.

Гаралт

Эхний мөрөнд сүлжээний хэрэглэгчдийн тоо $n$ бүхэл тоог оруулна. Дараагийн $n$ мөрүүд нь хэрэглэгч бүрийн санал болгосон найзуудын тоог хэвлэнэ. $i$-р мөрөнд $c_{i}$ хэрэглэгчийн нэр болон түүний санал болгосон найзуудын тоо $d_{i}$-г зай аваад хэвлэнэ.

Хэрэглэгчийн талаарх мэдээллийг ямар ч дарааллаар хэвлэж болно.

Орчуулсан: Даариймаа

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

Оролт
5
Mike Gerald
Kate Mike
Kate Tank
Gerald Tank
Gerald David
Гаралт
5
Mike 1
Gerald 1
Kate 1
Tank 1
David 2
Оролт
4
valera vanya
valera edik
pasha valera
igor valera
Гаралт
5
valera 0
vanya 3
edik 3
pasha 3
igor 3

Тэмдэглэл

Эхний жишээнд хэрэглэгч David-г авч үзье. Хэрэглэгч Mike, Tank нар David-тэй нэг ерөнхий найзтай (тэр нь Gerald). Хэрэглэгч Kate нь David-тэй ерөнхий найзгүй. Учир нь David-н санал болгосон найзууд нь Mike ба Tank юм.

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