| Codeforces Round 254 (Div. 2) |
|---|
| Закончено |
DZY любит химию, он обожает смешивать химикаты.
У DZY есть n химических веществ, m пар из них реагируют друг с другом. Он хочет вылить все эти вещества в пробирку одно за другим в некотором порядке.
Определим величину опасности вещества в пробирке. Опасность пустой пробирки равна 1. Каждый раз, когда DZY подливает в пробирку вещество, которое реагирует хотя бы с одним веществом, уже находящимся в данный момент в пробирке, опасность вещества пробирки умножается на 2. В противном случае опасность не изменяется.
Какую максимально возможную опасность вещества можно получить в итоге, после выливания в пробирку всех n веществ в оптимальном порядке?
В первой строке записано два целых числа через пробел, n и m 
.
В каждой из следующих m строк записано два целых числа через пробел, xi и yi (1 ≤ xi < yi ≤ n). Эти числа обозначают, что вещество xi вступит в реакцию с веществом yi. Любая пара реагирующих веществ встречается во входных данных не более одного раза.
Считайте, что все вещества пронумерованы от 1 до n в некотором порядке.
Выведите единственное целое число — максимальную возможную опасность.
1 0
1
2 1
1 2
2
3 2
1 2
2 3
4
В первом примере существует один способ смешать вещества, опасность при нем не возрастет.
Во втором примере порядок не имеет значения. В обоих случаях опасность будет равняться 2.
В третьем примере есть четыре способа достичь максимально возможной опасности: 2-1-3, 2-3-1, 1-2-3 и 3-2-1 (номера веществ в порядке наливания в пробирку).
