dlaud5379   1년 전

(DeepL로 한국어로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)

문제

JAG대학교 ICPC학과에는 N명의 재학생이 있으며, 각 학생에게는 1부터 N까지의 학번이 부여되어 있다. 또한, 학생들 사이의 친구 관계는 M개 존재한다. i번째 친구 관계는 ai와 bi의 순서쌍으로 나타낼 수 있으며, 학생 ai와 bi가 친구이고 서로 연락을 주고받을 수 있음을 의미한다.

학과 기말고사에서는 총 N과목의 시험을 실시할 예정이다. 학생 i는 i번 과목의 족보를 가지고 있다. 당신은 학생 1이다. 친구들끼리 족보 공유를 반복할 때 몇 과목의 족보를 모을 수 있는지 궁금해진 당신은 친구들끼리 족보를 K번 공유했을 때 족보 개수의 기댓값을 구하려고 한다.

다음 연산을 순서대로 K회 독립시행한다고 하자.

  • M개의 친구 관계 중 하나가 무작위로 선택되어 두 학생이 연락을 주고받는다. 이때 두 학생은 각자 가지고 있는 모든 족보를 공유한다.
    • 즉, 두 학생이 가지고 있는 족보의 집합을 각각 X와 Y라고 할 때, 시행 이후 두 학생이 가지고 있는 족보의 집합은 모두 X ∪ Y가 된다.

K회의 시행이 끝난 뒤, 학생 1인 당신이 가지고 있게 되는 족보 수의 기댓값을 모듈로 998,244,353 위에서 구하여라.

문제에서 구하는 기댓값은 항상 유리수이고, 문제의 제한 이내에서 기댓값을 P/Q로 나타낼 때 Q ≢ 0 (mod 998,244,353)임을 보일 수 있으며, 여기에서 R × Q ≡ P (mod 998,244,353), 0 ≤ R < 998,244,353을 만족하는 정수 R이 유일하게 결정된다. 이 R이 모듈로 998,244,353 위의 기댓값이다. 998,244,353 = 223 × 7 × 17 + 1은 소수이다.

입력

입력은 최대 50개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 다음과 같은 형식으로 주어진다.

N M K
a1 b1
...
aM bM

첫째 줄에는 학생 수 N, 친구 관계의 개수 M, 시행 횟수 K가 주어진다. (2 ≤ N ≤ 10, 1 ≤ M ≤ N(N-1)/2, 1 ≤ K ≤ 50)

둘째 줄부터 M줄에 걸쳐 친구 관계가 주어진다. 이 중 i번째 줄에는 ai와 bi가 주어진다. (1 ≤ ai, bi ≤ N) 자기 자신과 친구인 경우는 없다. 즉, 모든 1 ≤ i ≤ M에 대해 ai ≠ bi이다. 또한, 같은 친구 관계가 여러 번 주어지지 않는다. 즉, 모든 1 ≤ i, j ≤ M에 대해 i ≠ j이면 {ai, bi} ≠ {aj, bj}이다.

입력의 마지막 줄에는 0이 3개 주어진다.

출력

각 테스트 케이스마다 정답을 한 줄로 출력한다.

댓글을 작성하려면 로그인해야 합니다.