15 августа 2008 года Михаил Кузнецов и Дмитрий Ларионов, гребцы из Нижнего Тагила, завоевали бронзовую олимпийскую медаль в соревнованиях каноэ-двоек.

После этого правительство области решило поддержать школу гребного слалома «Полюс» в Нижнем Тагиле, вырастившую спортсменов. В школе на тот момент тренировались n молодых каноистов. Директор школы сообщил, что в годы, предшествующие олимпиаде, m экипажей каноэ-двоек, составленных из учеников школы, занимали призовые места на всероссийских соревнованиях. При этом некоторые каноисты поднимались на пьедестал в составе разных экипажей. Директор попросил выплатить премии спортсменам таким образом, чтобы члены каждого из экипажей-призёров в сумме получили не менее k рублей.

Однако из-за начавшегося экономического кризиса чиновники из министерства физической культуры и спорта решили потратить как можно меньше денег на выполнение просьбы директора школы. Какие премии были выплачены молодым спортсменам?

В первой строке записаны целые числа n, k и m (2 ≤ n ≤ 500; 1 ≤ k ≤ 10000; 0 ≤ m ≤ 100000). В каждой из следующих m строк записаны два различных целых числа — номера спортсменов из экипажа, ранее занимавшего призовое место. Ученики школы занумерованы целыми числами от 1 до n. Каждый экипаж-призёр встречается в списке ровно один раз.

Выведите в i-й строке размер премии, которую получил i-й спортсмен с абсолютной погрешностью не более 10⁻⁶. Если существуют несколько правильных ответов, выведите любой из них.