Star Tree

정점에 $1$부터 $N$까지 번호가 붙은 트리가 주어진다. 처음에 모든 정점의 값은 $0$이다.

다음과 같은 쿼리를 $Q$개 처리한다.

• $x\ y$: 정점 $x$에서 정점 $y$로 가는 유일한 단순 경로의 정점을 순서대로 $a_1,a_2,\ldots,a_k$라 하자. 각 에 대해 정점 의 값에 를 더한다. 여기서 , 이고, 이다.

경로의 양 끝 정점도 포함한다. 쿼리의 방향에 따라 더하는 값이 달라질 수 있다. 모든 쿼리를 처리한 뒤 각 정점의 값을 $998\,244\,353$으로 나눈 나머지를 구하여라.

입력은 다음과 같은 형식으로 주어진다. 첫째 줄에 정점의 수 $N$과 쿼리의 수 $Q$가 주어진다. 다음 $N-1$개 줄의 $u_i,v_i$는 트리의 간선을 나타내고, 다음 개 줄의 는 쿼리를 나타낸다. 이면 간선 줄은 없고, 이면 쿼리 줄은 없다.

정점 $1,2,\ldots,N$의 최종 값을 각각 $998\,244\,353$으로 나눈 나머지를 공백으로 구분하여 한 줄에 출력한다.

• $1\leq N\leq500\,000$.
• $0\leq Q\leq500\,000$.
• $1\le u_i$, ().