F. Цветные работы
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Gold14526 — художник. Он может рисовать $$$n$$$ цветами, пронумерованными $$$1, 2, \ldots, n$$$. Цвет $$$i$$$ имеет ограничивающий интервал $$$[l_i, r_i]$$$.

Работой называется корневое дерево $$$T=(V,E)$$$, в котором каждое ребро окрашено (одним из $$$n$$$ цветов). Работа называется красочной, если выполнены следующие условия:

  • Для любых трёх вершин $$$u, v, w \in V$$$, если рёбра $$$(u,v)$$$ и $$$(v,w)$$$ оба существуют, они должны иметь разные цвета.
  • Для всех цветов $$$i \in [1,n]$$$ пусть $$$d(u,i)$$$ обозначает количество рёбер цвета $$$i$$$ на простом пути от вершины $$$u$$$ до корня. Тогда $$$\max_{u \in V} d(u,i) \in [l_i, r_i]$$$.

Две работы $$$T=(V,E)$$$ и $$$T'=(V',E')$$$ называются изоморфными тогда и только тогда, когда выполнены следующие два условия:

  • $$$\lvert V\rvert = \lvert V'\rvert$$$;
  • Существует биекция $$$f:V \to V'$$$ такая, что:
    • Пусть $$$r$$$ — корень $$$T$$$, а $$$r'$$$ — корень $$$T'$$$. Тогда $$$f(r) = r'$$$;
    • Для любого $$$(u,v) \in E$$$ выполняется $$$(f(u),f(v)) \in E'$$$, и цвет ребра $$$(u,v)$$$ совпадает с цветом ребра $$$(f(u),f(v))$$$.

Gold14526 хочет узнать максимальное количество красочных работ, которые он может выбрать так, чтобы работы были попарно неизоморфны. Выведите ответ по модулю $$$\bf2$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1\le n\le 2\cdot 10^6$$$) — количество цветов.

Следующие $$$n$$$ строк содержат по два целых числа: $$$i$$$-я из них содержит $$$l_i$$$ и $$$r_i$$$ ($$$0\le l_i\le r_i\le 2\cdot 10^5$$$, $$$r_i\ge 1$$$) — ограничивающий интервал $$$i$$$-го цвета.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^6$$$.

Пусть $$$m=\max_{i=1}^n r_i$$$. Тогда гарантируется, что сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$0$$$ или $$$1$$$ — максимальное количество работ, которые можно выбрать, по модулю $$$2$$$.

Пример
Входные данные
4
2
0 1
0 1
2
1 1
1 1
3
0 2
0 1
0 1
3
1 2
1 1
1 1
Выходные данные
1
0
1
1
Примечание

В первом наборе входных данных ограничения для обоих цветов равны $$$[0, 1]$$$. Это означает, что на любом простом пути от корня может быть не более $$$1$$$ ребра цвета $$$1$$$ и не более $$$1$$$ ребра цвета $$$2$$$. Существует ровно $$$9$$$ допустимых попарно неизоморфных деревьев:

  • $$$1$$$ дерево с $$$1$$$ вершиной: только корень.
  • $$$2$$$ дерева с $$$2$$$ вершинами: корень соединён с потомком ребром цвета $$$1$$$ или ребром цвета $$$2$$$.
  • $$$3$$$ дерева с $$$3$$$ вершинами:
    • корень соединён с двумя потомками рёбрами цветов $$$1$$$ и $$$2$$$ соответственно.
    • путь из $$$2$$$ рёбер от корня, окрашенных $$$1$$$, затем $$$2$$$.
    • путь из $$$2$$$ рёбер от корня, окрашенных $$$2$$$, затем $$$1$$$.
  • $$$2$$$ дерева с $$$4$$$ вершинами:
    • корень имеет потомка через цвет $$$1$$$ (у которого есть потомок через цвет $$$2$$$) и ещё одного потомка через цвет $$$2$$$.
    • корень имеет потомка через цвет $$$2$$$ (у которого есть потомок через цвет $$$1$$$) и ещё одного потомка через цвет $$$1$$$.
  • $$$1$$$ дерево с $$$5$$$ вершинами: корень соединён с двумя потомками цветами $$$1$$$ и $$$2$$$, и каждый из этих потомков имеет ровно одного потомка противоположного цвета.
Так как $$$9 \equiv 1 \pmod 2$$$, ответ равен $$$1$$$.

Во втором наборе входных данных ограничения для обоих цветов равны $$$[1, 1]$$$. Каждое допустимое дерево должно удовлетворять условию, что максимальное количество рёбер каждого цвета на путях равно ровно $$$1$$$. Следовательно, дерево должно содержать хотя бы одно ребро цвета $$$1$$$ и хотя бы одно ребро цвета $$$2$$$. Существует ровно $$$6$$$ допустимых деревьев:

  • $$$3$$$ дерева с $$$3$$$ вершинами: корень соединён с двумя потомками цветами $$$1$$$ и $$$2$$$; путь, окрашенный $$$1$$$ затем $$$2$$$; путь, окрашенный $$$2$$$ затем $$$1$$$.
  • $$$2$$$ дерева с $$$4$$$ вершинами: те же два дерева с $$$4$$$ вершинами, что описаны в первом наборе входных данных.
  • $$$1$$$ дерево с $$$5$$$ вершинами: то же дерево с $$$5$$$ вершинами, что описано в первом наборе входных данных.
Так как $$$6 \equiv 0 \pmod 2$$$, ответ равен $$$0$$$.