Codeforces Beta Round 22 (Див. 2) |
---|
Закончено |
Вася устроился на работу системным администратором в корпорацию X. Первым его заданием было соединить n серверов с помощью m двусторонних прямых соединений так, чтобы данные с любого сервера можно было передать на любой другой по проложенной сети. Каждое прямое соединение должно соединять два различных сервера, причем между каждой парой серверов должно быть не более одного прямого соединения. Корпорация Y, конкурент корпорации X, сделала Васе предложение, от которого он не смог отказаться: Вася должен проложить сеть так, чтобы в случае выхода из строя сервера с номером v, передача данных между некоторыми двумя серверами, отличными от v, становилась невозможной, то есть сеть переставала быть связной. Помогите Васе проложить сеть.
В первой строке входных данных через пробел записаны 3 целых числа n, m, v (3 ≤ n ≤ 105, 0 ≤ m ≤ 105, 1 ≤ v ≤ n), n — число серверов, m — число прямых соединений, v — номер сервера, при поломке которого должна ломаться вся сеть.
Если искомой схемы соединений не существует, выведите -1. Иначе выведите m строк по 2 числа в каждой — описание всех прямых соединений в сети. Каждое прямое соединение описывается двумя числами — номерами двух соединяемых серверов. Серверы нумеруются начиная с 1. Если решений несколько, выведите любое.
5 6 3
1 2
2 3
3 4
4 5
1 3
3 5
6 100 1
-1
Название |
---|