|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
friends
Какую команду можно считать дружной? Ту, в которой каждый дружит с каждым? Так практически не бывает, особенно в больших командах: маловероятно, чтобы директор Медведев дружил и с инженером Кошкиным, и с уборщицей Зайкиной, и с продажником Белкиным... Но на практике команду можно считать дружной, если от любого её члена к любому можно протянуть цепочку дружб: Медведев дружит с Волковым, Волков с Рысевой, Рысева с Лосевым, Лосев с Зайкиной - вот и выстроилась цепочка. Но такая цепочка должна существовать для любой пары членов команды.
Разработайте программу, которая по данным о составе команды и о дружбах внутри неё определяет, дружная ли это команда.
Входные данные. В первой строке - разделённые пробелом натуральные числа N (количество участников команды) и M (количество дружб внутри неё). Оба числа не превышают 100. В следующих M строках - описания дружб: пары разделённых пробелами натуральных чисел, номеров участников. При этом дружба симметрична: если А дружит с В, то и В дружит с А, порядок номеров в паре безразличен, но дружба будет описана лишь один раз.
Выходные данные. Если команда дружная, програма должна вывести ":)", в протитвном случае выводится ":(".
Пример. При вводе данных
5 5
3 1
4 5
1 2
3 4
2 3
программа должна вывести
:)
А вот при вводе
5 4
3 1
4 5
1 2
2 3
выведется
:(
Для отправки решений необходимо выполнить вход.
|