Алиса только что создала схему с \(n\) лампочками и \(2n\) переключателями. Каждый компонент (лампочка или переключатель) имеет два состояния: включен или выключен. Лампочки и переключатели расположены таким образом:
- Каждая лампочка подключена к ровно двум переключателям.
- Каждый переключатель подключен к ровно одной лампочке. Неизвестно, к какой лампочке подключен каждый переключатель.
- Когда все переключатели выключены, все лампочки также выключены.
- Если переключатель переключается (с включенного на выключенный или наоборот), состояние лампочки, к которой он подключен, также переключается.
Алиса принесла схему, которая показывает только состояния \(2n\) переключателей, своей сестре Ирис и задала ей загадку: каково минимальное и максимальное количество лампочек, которые могут быть включены?
Зная проделки своей младшей сестры слишком хорошо, Ирис не тратит больше секунды, чтобы дать Алисе правильный ответ. Можете ли вы сделать также?
Выходные данные
Для каждого набора входных данных выведите два целых числа — минимальное и максимальное количество лампочек, которые могут быть включены, соответственно.
Примечание
В первом наборе входных данных в схеме только одна лампочка, и ни один переключатель не включен, поэтому лампочка точно выключена.
Во втором наборе входных данных в схеме только одна лампочка, но один переключатель, подключенный к ней, включен, поэтому лампочка включена.
В третьем наборе входных данных в схеме только одна лампочка, оба переключателя включены, поэтому лампочка выключена, так как переключается дважды.
В четвёртом наборе входных данных, чтобы не было включенных лампочек, переключатели могут быть расположены следующим образом:
- Переключатель \(1\) и переключатель \(4\) подключены к лампочке \(1\). Поскольку оба переключателя выключены, лампочка \(1\) также выключена.
- Переключатель \(2\) и переключатель \(6\) подключены к лампочке \(2\). Поскольку оба переключателя выключены, лампочка \(2\) также выключена.
- Переключатель \(3\) и переключатель \(5\) подключены к лампочке \(3\). Оба переключателя включены, поэтому лампочка \(3\) переключается дважды из своего первоначального выключенного состояния и, следовательно, также остается выключенной.
А чтобы включить \(2\) лампочки, переключатели могут быть расположены следующим образом:
- Переключатель \(1\) и переключатель \(2\) подключены к лампочке \(1\). Поскольку оба переключателя выключены, лампочка \(1\) также выключена.
- Переключатель \(3\) и переключатель \(4\) подключены к лампочке \(2\). Поскольку переключатель \(3\) включен, а переключатель \(4\) выключен, лампочка \(2\) переключается один раз из своего первоначального выключенного состояния, поэтому она включена.
- Переключатель \(5\) и переключатель \(6\) подключены к лампочке \(3\). Поскольку переключатель \(5\) включен, а переключатель \(6\) выключен, лампочка \(3\) переключается один раз из своего первоначального выключенного состояния, поэтому она включена.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1
0 0
1
0 1
1
1 1
3
0 0 1 0 1 0
3
0 1 1 1 0 0
|
0 0
1 1
0 0
0 2
1 3
|