Párok
Egy rendezvényre sok vendéget hívtak meg. Minden vendég előre megadta, hogy mikor érkezik és mikor távozik. A rendezők fényképeken akarják megörökíteni a résztvevőket. Két feltételt kell teljesíteni:
- Minden képen pontosan két vendég legyen rajta.
- Minden vendég legfeljebb egy képen szerepelhet.
Természetesen két vendég csak akkor szerepelhet közös képen, ha van olyan F időpont, amikor mindketten jelen vannak. Egy vendég csak akkor van jelen egy F időpontban, ha E érkezési és T távozási idejére E<=F<T.
Feladat
Készíts programot, ami kiszámítja, hogy legjobb esetben hány fénykép készülhet, és
megadja, hogy mely párok szerepelnek a fényképeken.
Bemenet
A bemenet első sora a vendégek számát adja meg (1<=N<30000), majd N sorban
a vendégek érkezési és távozási ideje olvasható (1<=E<T<20000).
Kimenet
Az első sorba a fényképek maximális számát kell írni, utána pedig egy lehetséges megoldást: soronként egy párt, ahol a vendégeket sorszámukkal adjuk meg.
Példa
| parok.be | parok.ki |
8 1 3 2 5 2 3 8 10 2 4 4 7 5 8 7 8 |
3 1 3 5 2 6 7 |