Помимо жалоб на уличное освещение, в мэрию Бергорода регулярно поступают жалобы на неполадки с радиовещанием в черте города. Всего в мэрию поступило $$$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$$$).