В качестве внеконкурсного мероприятия на «Russian Code Cup» было решено поиграть в футбол. Все участники разделились на n команд и провели несколько матчей, при этом две команды не могли сыграть друг против друга более одного раза.
Судьей назначили самого опытного участника — Павла. Но так как он был самым мудрым из всех, ему сразу наскучили игры, и он уснул. Проснувшись, он обнаружил, что турнир закончился, и команды хотят узнать результаты всех матчей.
Чтобы никто не обнаружил, что Павел заснул и не следил за результатами, он решил восстановить исходы всех матчей. Для этого он опросил все команды и узнал, что победила дружба, а именно каждая команда выиграла у других ровно k раз. Помогите Павлу придумать хронологию турнира, удовлетворяющую всем условиям или сообщите, что ее не существует.
Выходные данные
В первой строке выведите целое число m — количество сыгранных матчей. В следующих m строках должна содержаться информация обо всех матчах, по матчу в строке. В i-й строке выведите два целых числа ai bi (1 ≤ ai, bi ≤ n; ai ≠ bi). Числа ai, bi обозначают, что в i-м матче команда с номером ai победила команду с номером bi. Считайте, что команды пронумерованы от 1 до n.
Если не существует турнира, удовлетворяющего условию задачи, выведите -1.