Лиса Ciel и ее друзья стоят в танцевальной комнате. Там n мальчиков и m девочек, и они еще не танцевали. На танцах будут ставить песни и во время каждой песни должны танцевать ровно один мальчик и одна девочка. Также есть особое правило:
- или мальчик в танцующей паре должен танцевать в первый раз (то есть он не танцевал ни с кем ранее);
- или девочка в танцующей паре должна танцевать в первый раз.
Помогите лисе Ciel и составьте расписание, по которому танцы растянутся на как можно больше песен.
Выходные данные
В первой строке выведите k — количество песен, которые можно будет протанцевать. Затем на следующих k строках выведите порядковые номера мальчиков и девочек, танцующих во время песен, в хронологическом порядке. Считайте, что мальчики пронумерованы от 1 до n, а девочки пронумерованы от 1 до m.
Примечание
В первом тесте есть 2 мальчика и 1 девочка. Можно провести 2 танца: 1-ый мальчик и 1-ая девочка (во время первой песни), 2-ой мальчик и 1-ая девочка (во время второй песни).
Во втором тесте есть 2 мальчика и 2 девочки, ответ — 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
|
2
1 1
2 1
|
|
2
|
2 2
|
3
1 1
1 2
2 2
|