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 |