DZY любит химию, он обожает смешивать химикаты.
У DZY есть n химических веществ, m пар из них реагируют друг с другом. Он хочет вылить все эти вещества в пробирку одно за другим в некотором порядке.
Определим величину опасности вещества в пробирке. Опасность пустой пробирки равна 1. Каждый раз, когда DZY подливает в пробирку вещество, которое реагирует хотя бы с одним веществом, уже находящимся в данный момент в пробирке, опасность вещества пробирки умножается на 2. В противном случае опасность не изменяется.
Какую максимально возможную опасность вещества можно получить в итоге, после выливания в пробирку всех n веществ в оптимальном порядке?
Выходные данные
Выведите единственное целое число — максимальную возможную опасность.
Примечание
В первом примере существует один способ смешать вещества, опасность при нем не возрастет.
Во втором примере порядок не имеет значения. В обоих случаях опасность будет равняться 2.
В третьем примере есть четыре способа достичь максимально возможной опасности: 2-1-3, 2-3-1, 1-2-3 и 3-2-1 (номера веществ в порядке наливания в пробирку).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 0
|
1
|
|
2
|
2 1
1 2
|
2
|
|
3
|
3 2
1 2
2 3
|
4
|