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
|
Tesztadatok
