놀이공원

새 놀이공원의 프로젝트를 감독하는 일을 맡았다. 이 놀이공원에는 특별한 장치가 있다. 손님을 한 놀이기구에서 다른 놀이기구로 빠르고 재미있게 옮겨 줄 수 있는 방향이 있는 미끄럼틀이다.

공원 소유주가 현재 프로젝트를 넘겼다. 계획된 놀이기구 목록과 그 사이에 지어야 할 미끄럼틀 목록이다. 그런데 소유주는 사업가라서 불가능한 것도 구상했다. 예를 들어 귀신의 성에서 롤러코스터로, 롤러코스터에서 낙하탑으로, 낙하탑에서 다시 귀신의 성으로 가는 미끄럼틀을 계획했다. 미끄럼틀은 아래로만 내려갈 수 있으므로 이것은 문제가 된다. 공원을 지을 때 물리 법칙을 무시할 수 없으니 프로젝트 변경을 요청해야 한다. 낙하탑과 귀신의 성 사이 미끄럼틀의 방향을 뒤집는 것은 받아들여 줄지도 모른다.

형식적으로 정리하면 다음과 같다.

• 프로젝트는 놀이기구 목록과 방향이 있는 미끄럼틀 목록이다. 각 미끄럼틀은 한 놀이기구에서 시작해 다른 놀이기구에서 끝난다.
• 제안은 프로젝트에서 일부 미끄럼틀(하나도 뒤집지 않거나 전부 뒤집는 경우 포함)의 방향을 뒤집어 얻는다.
• 제안은 모든 미끄럼틀이 아래로 내려가도록 각 놀이기구에 높이를 줄 수 있으면 적법하다.
• 제안의 비용은 방향을 뒤집은 미끄럼틀의 수다.

주어진 프로젝트에 대해 모든 적법한 제안의 비용 합을 구하라. 이 값은 998,244,353으로 나눈 나머지를 출력한다.

첫 줄에 두 정수 n, m이 주어진다 (1 ≤ n ≤ 18, 0 ≤ m ≤ n(n − 1)/2). n은 놀이기구의 수, m은 미끄럼틀의 수다. 놀이기구에는 1부터 n까지 번호가 매겨진다.

이어서 m개의 줄이 주어진다. i번째 줄에는 두 정수 a_i, b_i (1 ≤ a_i, b_i ≤ n)가 주어지며, a_i에서 b_i로 가는 미끄럼틀을 뜻한다. 다음을 가정해도 된다.

• 자기 자신으로 가는 미끄럼틀은 없다. 모든 i에 대해 a_i ≠ b_i이다.
• 같은 미끄럼틀은 두 번 나오지 않는다. i ≠ j이면 a_i ≠ a_j 또는 b_i ≠ b_j이다.
• 두 놀이기구가 양방향으로 연결되지 않는다. 순서를 무시한 쌍 {a_i, b_i}는 모두 다르다.

모든 적법한 제안의 비용 합을 998,244,353으로 나눈 나머지를 한 줄에 정수 하나로 출력한다.

첫 번째 예시에는 제안이 두 개 있다. 미끄럼틀 방향을 뒤집지 않으면 비용은 0이고, 뒤집으면 비용은 1이다. 둘 다 적법하므로 답은 0 + 1 = 1이다.

두 번째 예시에는 제안이 여덟 개 있다. 제안 1 → 2, 2 → 3, 3 → 1은 미끄럼틀 열 1 → 2 → 3 → 1 때문에 놀이기구 1이 자기 자신보다 높아야 하므로 적법하지 않다. 제안 2 → 1, 3 → 2, 1 → 3도 같은 이유로 적법하지 않다. 나머지 여섯 개는 적법하며 비용은 0, 1, 2, 1, 2, 3이다. 답은 0 + 1 + 2 + 1 + 2 + 3 = 9이다.