3393: E.From Tree to Graph

Bobo has a tree of n vertices numbered with 0, 1, . . . , (n − 1). He subsequently adds m edges between vertex xi and LCA(xi, yi ) where LCA(xi, yi) is the vertex lying on the unique tree path between vertex xi and yi and closest to the vertex 0.

 Let the graph obtained by adding the edges {(x1, LCA(x1, y1)), (x2, LCA(x2, y2)), . . . , (xi , LCA(xi, yi))} to the tree be Gi, and fi(u) be the number of connected components after the removal of vertex u from Gi. Bobo knows that for i {0, 1, 2, . . . , m}

z_i = f_i(0) ⊕f_i(1) ⊕· · · ⊕f_i(n − 1).

(⊕ denotes xor.)

 Given a, b, x₀, y₀, he also knows that for i {1, 2, . . . , m},

• x_i = (a · x_i−1 + b · y_i−1 + z_i−1) mod n,

• y_i = (b · x_i−1 + a · y_i−1 + z_i−1) mod n. Help him to find x_m, y_m.

The input consists of several test cases and is terminated by end-of-file.

 The first line of each test case contains six integers n, m, a, b, x0, y0. The i-th of the following (n − 1) lines contains two integers u_i and v_i, which denotes the tree edge between vertex u_i and v_i.

For each test case, print two integers which denote x_m, y_m.

 Constraint

 • 2 ≤ n ≤ 5000

 • 1 ≤ m ≤ n²

 • 0 ≤ a, b, x₀, y₀, u_i, v_i < n

 • The sum of n does not exceed 25, 000.

4 1 1 0 2 3
0 1
1 2
0 3
4 2 1 0 2 0
0 1
1 2
2 3
5 25 1 2 3 4
0 1
0 2
1 3
1 4

2 3
1 3
1 0