Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Midász király arról a képességéről volt ismert, hogy amihez hozzáért, arannyá változott. Azt azonban későn vette észre, hogy ennek a képességének óvatlan használatával komoly kárt okozhat önmagának. Így például rézpénzekből, ezüstpénzekből és vaspénzekből álló teljes érmegyűjteményét használhatatlan aranyakká változtatta. Mindent elveszítve, ami neki valaha fontos volt, elhatározta, hogy idejét a lehető legártalmatlanabb módon tölti, és elkezdte a következő játékot játszani.
Egy tábla van előtte \(N\) oszloppal és \(N\) sorral. Ezen a táblán sok-sok aranypénze közül \(N\) darab helyezkedik el. Minden aranypénz pontosan egy mezőt foglal el a táblán, és egy mezőn nem lehet két aranypénz. Midász egy másodperc alatt felvehet egy aranyat, és áthelyezheti azt egy olyan mezőre, amelynek közös oldala van azzal a mezővel, ahol ez az arany éppen elhelyezkedik, de csak olyan mezőre teheti, amely nem foglalt. Midász célja az, hogy minden sorban, és minden oszlopban egy aranypénz legyen.
Midász már meglehetősen ügyes ebben a játékban, de az érdekli hogy eléri-e célját a lehető legrövidebb idő alatt. Tekintettel arra, hogy nem szeretné a billentyűzetét is arannyá változtatni, arra kér titeket, számítsátok ki neki ezt. Azt várja el tőletek, hogy az aranypénzek adott kezdeti elhelyezkedésére, számítsátok ki neki, mennyi az a legrövidebb idő, amely alatt befejezheti a játékot?
A szabványos bemenet első sora az \(N\) számot, a sorok, oszlopok és aranyak számát tartalmazza. A következő \(N\) sor két számot tartalmaz, \(r_i\) és \(c_i\) természetes számokat, amelyek azt mutatják, hogy kezdetben az \(i\)-edik arany az \(r_i\) sor és \(c_i\) oszlop metszéspontjában található.
A szabványos kimenet első és egyetlen sorában egy számot íratni ki: a másodpercek legkisebb számát, amely szükséges, hogy Midász befejezze a játékot az aranypénzek adott kezdeti elhelyezkedése esetén.
3
2 1
2 2
2 323
1 2
3 1
2 30Az első tesztpélda esetén Midásznak legalább két másodpercre van szüksége, hogy ne legyen két aranypénz a második sorban. Úgy győzhet két lépésben, hogy az aranyat a \((2,2)\) mezőről áthelyezi az \((1,2)\) mezőre, a \((2,1)\) mezőről pedig a \((3,1)\) mezőre.
A második tesztpélda esetében Midásznak semmit sem kell tennie ahhoz, hogy befejezze a játékot.
A tesztpéldák 4 független csoportba oszthatók: