Совсем недавно в Берляндии завершился турнир по скоростному засыпанию «Соня-2010». В турнире приняло участие n сильнейших участников со всей страны. Турнир состоит из игр, каждая из которых является противостоянием двух участников. Таким образом, в процессе турнира было проведено n·(n - 1) / 2 игр, то есть каждый из участников встретился с каждым.
Правила игры очень просты — кто первый засыпает, тот и победил. Ответственный секретарь должен был записать каждую игру в виде пары чисел «xi yi», где xi и yi — это порядковые номера участников игры, причем тот, кто записан первым является победителем игры (т.е. xi — победитель, а yi — проигравший). Ничьих в этой игре не бывает.
Совсем недавно «Институт Изучения Сна» выяснил, что на самом деле каждый человек характеризуется величиной pj — скоростью засыпания в экстремальных условиях. Таким образом, при игре двух игроков побеждает тот, у кого эта величина меньше. Величина pj у каждого человека своя и не изменяется в течении жизни.
Известно, что у всех участников турнира их pj различны. Также известно, что секретарь сделал записи результатов всех игр, кроме одной.
Ваша задача написать программу, которая по заданным записям результатов игр определяет недостающую.
В первой строке записано целое число n (3 ≤ n ≤ 50) — количество участников. Следующие n·(n - 1) / 2 - 1 строк содержат результаты всех игр. Каждая игра записана в отдельной строке в виде пары чисел xi, yi (1 ≤ xi, yi ≤ n, xi ≠ yi), где xi и yi — номера участников встречи. Известно, что в процессе турнира каждый из n участников принял участие в n - 1 игре, встретившись со всеми соперниками.
Выведите пару чисел x y — недостающую запись. Если решений несколько, то выведите любое.
4
4 2
4 1
2 3
2 1
3 1
4 3
Название |
---|