Se citesc n activitati, numerotate de la 1 la n, fiecare caracterizata printr-un moment de inceput si unul de sfarsit. Determinati, folosind metoda Greedy, un subset maxim de activitati compatibile doua cate doua (care nu se suprapun) si afisati indicii activitatilor alese.
- Date de intrare
- Pe prima linie se citeste n. Urmeaza n linii, fiecare cu doua numere: momentul de inceput si cel de sfarsit al activitatii cu indicele respectiv.
- Date de iesire
- Pe prima linie se afiseaza numarul de activitati alese. Pe a doua linie se afiseaza indicii (numerotati de la 1) ai activitatilor alese, in ordinea selectiei (crescator dupa momentul de sfarsit), separati prin spatiu.
- Restrictii
- 1 <= n <= 100000, 0 <= inceput < sfarsit <= 10^9
Exemple
Exemplul 1
Intrare
3 1 2 2 3 3 4
Iesire
3 1 2 3
Exemplul 2
Intrare
4 1 3 2 4 3 5 0 6
Iesire
2 1 3