Limits 1s, 128 MB

After performing so badly in the World Cup, Mushfiq left cricket and started problem solving. You told him to solve the following problem.

You are given a rooted tree with nn vertices (each edge of the tree has a cost) and a magic integer xx. The vertices are numbered from 11 to nn, the root is the vertex number 11. You are also given an operation —

  • You can change the cost of an edge by multiplying it by any integer kk. For example, cost of an edge is pp, you can change it to qq such that q=pkq = p * k, where k1k≥1.

You have to find two integers nodeinode_i and kk such that length of the path from root to nodeinode_i is maximum, GCD of the costs of the path is a multiple of xx by applying the operation at most once and kk is minimum. If there are multiple nodes with maximum path length and minimum kk print the node with minimum label.


The first line contains two space separated integers nn and xx — the number of vertices and the magic integer.

Each of the next n1n−1 lines describes an edge of the tree. Edge ii is denoted by three integers uiu_i, viv_i and costicost_i— the labels of vertices it connects and cost of the edge.


1x,costi10181≤x, cost_i≤10^{18}

1ui,vin,uivi1≤u_i, v_i≤n, u_i≠v_i


Print two integers nodeinode_i and kk — if length of the path from root to nodeinode_i is maximum, GCD of the path is a multiple of xx and kk is minimum.


9 6
1 2 6
1 3 6
2 4 6
2 5 6
3 6 12
3 7 18
5 8 8
5 9 7
8 3

Test Case 1 Tree


Login to submit.


40% Solution Ratio
dip_BRUREarliest, 5M ago
sagorahmedmunnaFastest, 0.1s
RoyheroLightest, 40 MB
sagorahmedmunnaShortest, 1184B
Toph uses cookies. By continuing you agree to our Cookie Policy.