8530: Directed

NIO is playing a D\&D-like game.

In this game, the map can be concerned as a connected graph with N vertices and N−1 edges. The vertices are numbered from 1 to n and vertex 1 is the destination of his journey. Initially, all edges can be passed in both directions. At the beginning of the game, K edges will be randomly selected to become directed edges. All directed edges point to the destination which means he can only approach the destination along the directed edge. In this way, no matter which edge is selected, he can still reach the destination.

But unfortunately, NIO is a road nut. He started at vertex s. At each step, he will randomly select an available edge connected with the current vertex and move to the adjacent vertex.

NIO wanted to know how many steps he expected to take to reach the destination.

Since the answer is too large, NIO only wants to know it modulo 998244353.

The first line contains three integers N, K, and s (1≤N≤10⁶,0≤K≤N−1,1≤s≤N).
Each of the following N−1 lines contains two integers u_i and v_i(1≤u_i,v_i≤N,u_i≠v_i),describing an undirected edge (u_i,v_i)in the graph
It is guaranteed that the graph is connected and there is at most one edge between any pair of vertices.

A single non-negative integer, denoting the expectation, modulo 998244353.

5 2 4
1 2
2 3
3 4
2 5

332748124