A. Зам засах

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

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

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

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

$Х$ хот $n × n$ огтлолцолыг үүсгэж буй $n$ хөндлөн чиглэлтэй болон $n$ босоо чиглэлтэй хязгааргүй урттай замуудаас бүрдэнэ. Босоо болон хөндлөн замууд аль аль нь $1$-ээс $n$ хүртэл дугаарлагдах ба огтлолцолууд нь огтлолцолыг үүсгэж буй хоёр замын дугаараар тодорхойлогдоно.

Элсэн замууд хэрэглээнээс гараад удаж байгаа ба эдгээрийг засмал зам болгох шийдвэр гаргасан. Энэ ажлыг хийх ажилчдыг хөлслөсөн ба аль аль огтлолцолыг засмал болгох вэ гэх ажлын хуваарь гарсан.

Замын засвар нь $n^{2}$ өдөр үргэлжлэхээр төлөвлөгдсөн. Ажилчдын баг $i$-р өдрөө жагсаалтын $i$-р огтлолцол дээр ирэх ба огтлолцолыг үүсгэж буй хоёр замын аль нь ч засмал зам биш бол энэ 2 замыг засмал болгож засна. Бусад тохиолдолд юу ч хийлгүйгээр огтлолцлоос явна.

Зам засах ажлын хуваарийн дагуу ядаж нэг зам засагдах өдрүүдийг ол.

Оролт

Оролтын эхний мөрөнд $n$ ($1 ≤ n ≤ 50$) бүхэл тоон утга байх ба энэ нь хотын хөндлөн болон босоо замуудын тоо юм.

Дараагийн $n^{2}$ мөрөнд хуваарийн дагуу огтлолцолууд байна. Эдгээрийн $i$-р мөр бүр $h_{i}, v_{i}$ ($1 ≤ h_{i}, v_{i} ≤ n$) зайгаар тусгаарлагдсан хоёр тоог агуулах ба энэ нь цагийн хуваарийн $i$-р мөрөнд байгаа огтлолцол нь $h_{i}$ хөндлөн зам болон $v_{i}$-р босоо замын огтлолцол юм. Энэ нь бүх огтлолцолууд ялгаатай гэсэн үг юм.

Гаралт

Замын ажил үргэлжилж буй (зам засагдах) өдрүүдийг өсөх дарааллаар нэг мөрөнд хэвлэ. Өдрүүд $1$-ээс эхлэн дугаарлагдана.

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

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

Оролт
2
1 1
1 2
2 1
2 2
Гаралт
1 4 
Оролт
1
1 1
Гаралт
1 

Тэмдэглэл

Дээрх жишээн дээр бригад дараах байдлаар ажиллана:

  1. Эхний өдөр бригад 1-р хөндлөн чиглэлтэй зам болон 1-р босоо чиглэлтэй замын огтлолцол дээр ирнэ. Энэ 2 зам хоёулаа засмал биш учир ажилчид 1-р хөндлөн чиглэлтэй зам болон 1-р босоо чиглэлтэй замыг хоёуланг нь засмал болгож засна;
  2. Хоёр дахь өдөр ажилчдын бригад 1-р хөндлөн чиглэлтэй зам болон 2-р босоо чиглэлтэй замын огтлолцол дээр ирнэ. 2-р босоо чиглэлтэй зам засагдаагүй боловч 1-р хэвтээ чиглэлтэй зам эхний өдөр засагдсан учир ажилчид явах ба юуг ч засахгүй;
  3. Гурав дахь өдөр ажилчдын бригад 2-р хөндлөн чиглэлтэй зам болон 1-р босоо чиглэлтэй замын огтлолцол дээр ирнэ. 2-р хэвтээ чиглэлтэй зам засагдаагүй боловч 1-р босоо чиглэлтэй зам эхний өдөр засагдсан учир ажилчид явах ба юуг ч засахгүй;
  4. Дөрөв дахь өдөр бригад 2-р хөндлөн чиглэлтэй зам болон 2-р босоо чиглэлтэй замын огтлолцол дээр ирнэ. Энэ 2 зам хоёулаа засмал биш учир ажилчид 2-р хөндлөн чиглэлтэй зам болон 2-р босоо чиглэлтэй замыг хоёуланг нь засмал болгож засна;
Сэтгэгдлүүдийг ачааллаж байна...