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).

Í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!

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.

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!

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

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

Algoritmusok:

megoldás