Problem Description

Takahashi loves bridges very much. Therefore, he loves trees, which are graphs where every edge is a bridge (a term from graph theory). Also, Takahashi has recently learned about XOR in school. Thus, he is thinking about the following problem:

Given a connected undirected graph with $ N $ vertices and $ N-1 $ edges, which is a tree. Each vertex is named vertex $ 1 $, vertex $ 2 $, ..., vertex $ N $. Each edge has a non-negative integer cost assigned to it.

Given an integer $ X $, find the total number of pairs $ (a, b) $ ($ 1 ≤ a < b ≤ N $) such that the XOR sum of the costs of the edges on the simple path (a path that does not traverse the same edge twice, and there is always exactly one in a tree) connecting vertex $ a $ and vertex $ b $ equals $ X $. The XOR sum refers to the value obtained by bitwise exclusive OR (XOR) of several integers $ A_1, A_2, ... $ in their binary representations. For example, $ 1 $ XOR $ 2 $ XOR $ 5 $ is $ 6 $.

Your task is to solve this problem on behalf of Takahashi.

Input Format

The input is given from the standard input in the following format:

$ N $ $ X $ $ x_1 $ $ y_1 $ $ c_1 $ $ x_2 $ $ y_2 $ $ c_2 $ : $ x_{N-1} $ $ y_{N-1} $ $ c_{N-1} $

• The first line contains an integer $N\ (1 ≤ N ≤ 100,000)$ representing the number of vertices in the graph and an integer $X\ (0 ≤ X ≤ 10^9)$ mentioned in the problem statement.
• The following $ N-1 $ lines contain the information of the $ N-1 $ edges in the graph. The $ i $-th line ($ 1 ≤ i ≤ N-1 $) contains two integers $x_i, y_i\ (1 ≤ x_i, y_i ≤ N)$ representing the two vertices connected by the $ i $-th edge and an integer cost $c_i\ (0 ≤ c_i ≤ 10^9)$.
• It is guaranteed that the given graph is connected.

Output Format

Output the answer sought in the problem statement on the first line. Ensure to include a newline at the end.

Sample Input and Output

Sample Input #1

6 7
1 2 5
2 3 3
3 4 6
2 5 2
5 6 7

Sample Output #1

3

Sample Input #2

6 3
1 2 1
2 3 3
3 4 2
4 5 3
4 6 1

Sample Output #2

4

Sample Input #3

10 1
9 10 1
6 10 1
5 2 1
8 6 1
4 5 1
7 6 0
3 8 0
3 1 1
8 2 0

Sample Output #3

25

Notes/Hints

Sample Explanation 1

For $ (a, b) = (1, 5), (4, 5), (5, 6) $, the XOR sum of the costs of the edges on the path equals $ 7 $ (in binary $ 111 $), so the answer is $ 3 $. The graph for this input example is shown below. The costs are displayed in both decimal and binary notation.

见题面 Input 部分

见题面 Output 部分