Programozás‎ > ‎Feladatok‎ > ‎

Párok (2012)

Az iskola szalagavató bálján a 11. osztályosok tűzik ki a szalagokat a 12. osztályosokra. Mindenkiről tudjuk, hogy a másik osztályból kit ismer. A két osztály felsorakozik egymással szemben, de mindenki csak valamely ismerősének akarja kitűzni a szalagot. Feltesszük, hogy a két osztály azonos létszámú (mindkettőben N tanuló van).

Feladat

Írjunk programot, ami megadja, hogy egyszerre maximum hány 11. osztályos diák tűzheti ki úgy a szalagot valamely 12. osztályos ismerőse ruhájára, hogy a hozzálépése során egyik diák sem keresztezheti semelyik másik diák útját!

Bemenet

A bemenet első sorában három egész szám van egy szóközzel elválasztva, a tanulók N száma (1 <= N <= 500) és a baráti párok M száma (1 <= M <= 20000) van. A tanulókat mindkét osztályban az 1,…,N számokkal azonosítjuk. A következő M sor mindegyike két egész számot tartalmaz (egy szóközzel elválasztva): a baráti párokat.

Kimenet

A kimenet első sorába azon 11.-es tanulók maximális M számát kell írni, akik útjuk keresztezése nélkül odaléphetnek valamely 12.-es ismerősükhöz a szalagot kitűzni! A következő M sorban egy-egy pár 11.-es és 12.-es tagjának sorszáma szerepeljen, sorszám szerint növekvő sorrendben!

Példa

Bemenet  Kimenet
4 7
1 1
1 4
2 1
3 2
4 3
2 4
3 4
3
1 1
3 2
4 3


Tesztadatok

Címkék

A feladat forrása: NTOITV 2012 3. forduló, 11-13. évfolyam
Algoritmusok:

megoldás