Назовем лесом неориентированный граф без циклов (петли и кратные рёбра также запрещены). Однажды Миша играл с лесом из n вершин. Для каждой вершины v от 0 до n - 1 он записал два числа degreev и sv, где первое число — количество вершин, смежных с вершиной v, а второе — XOR-сумма номеров вершин, смежных с v (в случае, если смежных вершин не было, он записал 0).
На следующий день Миша не смог вспомнить, какой граф у него был изначально. У Миши остались значения degreev и sv. Помогите ему найти количество ребер и сами ребра исходного графа. Гарантируется, что существует лес, которому соответствуют выписанные Мишей числа.
Выходные данные
В первой строке выведите число m, количество ребер графа.
Далее выведите m строк, каждая из которых содержит два различных числа a и b (0 ≤ a ≤ n - 1, 0 ≤ b ≤ n - 1), соответствующие ребру (a, b).
Рёбра могут быть выведены в любом порядке; вершины одного ребра также могут быть выведены в любом порядке.
Примечание
XOR-суммой чисел называется результат побитового сложения чисел по модулю 2. Данная операция существует во многих современных языках программирования, например, в языках C++, Java и Python она обозначается как «^», а в Pascal — как «xor».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 3
1 0
1 0
|
2
1 0
2 0
|
|
2
|
2
1 1
1 0
|
1
0 1
|