1693: 트리의 깊이우선탐색의 개수

트리의 깊이우선탐색이란 다음과 같이 재귀적으로 정의된다. 
dfs(x):
x출력
for y in child_of_x
dfs(y)

여기서 x의 자식들 중 어떤 자식을 먼저 방문하는지에 대한 규칙은 따로 없기 때문에 깊이우선탐색의 결과 출력되는 순열은 다양하다.
예를 들어 n = 5 이고 트리가 다음과 같다면



아래처럼 4가지로 깊이우선탐색이 가능하다.
1 2 3 4 5
1 2 3 5 4
1 3 4 5 2
1 3 5 4 2


1을 루트로 하는 주어진 트리에서 서로 다른 깊이 우선 탐색의 결과의 개수를 구하는 프로그램을 작성하시오.


[출처] 2022 제3회 세종 정보올림피아드 대회 예선 문항h

첫 번째 줄에 원소의 수를 나타내는 자연수 n이 주어진다.
두 번째 줄부터 n-1줄에 걸쳐서 각 간선의 정보가 주어진다.
각 간선의 정보는 연결하는 정점의 번호를 공백으로 구분하여 주어진다.


[입려값의 범위]
n ≤ 300,000

서로 다른 깊이우선탐색의 개수를 출력한다. 단, 그 개수가 너무 커질 수 있기 때문에 998,244,353으로 나눈 나머지를 출력한다.

5
1 2
1 3
3 4
3 5

4