Помимо жалоб на уличное освещение, в мэрию Бергорода регулярно поступают жалобы на неполадки с радиовещанием в черте города. Всего в мэрию поступило \(n\) жалоб, подозрительно похожих друг на друга: в \(i\)-й жалобе очередной радиолюбитель упоминал две радиостанции \(x_i\) и \(y_i\), сигнал от которых принимается с помехами, и требовал, чтобы хотя бы одна из этих радиостанций распространяла свой сигнал по всему городу.
Конечно же, мэр Бергорода вплотную занялся рассмотрением этих жалоб. Недавно в Бергороде была установлена новая радиовышка, способная распространять сигнал силы от \(1\) до \(M\) (обозначим силу сигнала радиовышки за \(f\)). Мэр принял решение выбрать несколько радиостанций и заключить с ними договор, чтобы жители города могли принимать их сигнал. Для заключения договора с \(i\)-й радиостанцией необходимо, чтобы соблюдались следующие условия:
- мощность сигнала \(f\) должна быть не менее \(l_i\), иначе в некоторых районах города будет невозможно принимать сигнал \(i\)-й радиостанции;
- мощность сигнала \(f\) должна быть не более \(r_i\), иначе сигнал смогут принять жители других населенных пунктов, не заключившие договор с \(i\)-й радиостанцией.
Всего этого уже было достаточно, чтобы мэру было трудно выбрать мощность сигнала и радиостанции так, что все жалобы будут удовлетворены. Но позже выяснилось, что некоторые радиостанции могут использовать одни и те же частоты для распространения сигнала: всего существует \(m\) пар радиостанций (\(u_i\), \(v_i\)), использующих одни и те же частоты, и для каждой такой пары нельзя одновременно заключить договор с обеими радиостанциями. Если радиостанции \(x\) и \(y\) используют одни и те же частоты, и радиостанции \(y\) и \(z\) используют одни и те же частоты, это не значит, что радиостанции \(x\) и \(z\) используют одни и те же частоты.
Мэру очень трудно проанализировать всю эту информацию и понять, с какими радиостанциями нужно заключать договоры. Помогите ему выбрать такую мощность сигнала \(f\) и такое множество радиостанций, с которыми город заключит договоры, чтобы:
- все жалобы жителей были удовлетворены (формально, для каждого \(i \in [1, n]\) либо с радиостанцией \(x_i\), либо с радиостанцией \(y_i\) заключен договор);
- никакие выбранные радиостанции не конфликтовали за частоты (формально, для каждого \(i \in [1, m]\) либо с радиостанцией \(u_i\), либо с радиостанцией \(v_i\) не заключен договор);
- для каждой выбранной радиостанции соблюдаются условия на мощность сигнала (формально, для каждой выбранной радиостанции \(i\) соблюдается \(l_i \le f \le r_i\)).
Выходные данные
Если не существует такого значения мощности сигнала и такого множества радиостанций, при которых выполнялись бы все ранее описанные условия, выведите \(-1\).
Иначе в первой строке выведите два целых числа \(k\) и \(f\) — количество радиостанций в выбранном множестве и мощность сигнала соответственно. Во второй строке выведите \(k\) различных целых чисел от \(1\) до \(p\) — номера радиостанций, с которыми следует заключить договор (в любом порядке). Если возможных ответов несколько, выведите любой из них; не обязательно минизировать/максимизировать ни количество выбранных радиостанций, ни мощность сигнала.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 4 4 2
1 3
2 3
1 4
1 2
3 4
1 4
1 2
3 4
|
2 3
1 3
|
|
2
|
2 4 4 2
1 3
2 4
1 2
1 2
3 4
3 4
1 2
3 4
|
-1
|