XOR Distance in a Tree

You are given a tree with ( n ) cities (nodes) and ( n-1 ) roads (edges). Each road has a cost of 1. In this tree, for any two given cities ( a ) and ( b ) and an integer ( k ), your task is to determine whether there exists a city ( t ) such that

[ \mathrm{dis}(t,a) \oplus \mathrm{dis}(t,b) = k ]

where ( \mathrm{dis}(x,y) ) represents the distance (i.e. the number of roads on the unique path) between cities ( x ) and ( y ), and ( \oplus ) denotes the bitwise XOR operation.

Input Format:

• The first line contains an integer \( n \) denoting the number of cities.
• The following \( n-1 \) lines each contain two space-separated integers \( u \) and \( v \) denoting a road between cities \( u \) and \( v \).
• The last line contains three space-separated integers: \( a \), \( b \), and \( k \).

Output Format:

• Print "Yes" if there exists a city \( t \) satisfying the condition; otherwise, print "No".

Example:

Input:
5
1 2
1 3
3 4
3 5
2 5 2

Output:
No

Explanation: In the given tree, there is no city ( t ) such that ( \mathrm{dis}(t,2) \oplus \mathrm{dis}(t,5) = 2 ).

inputFormat

The input begins with an integer \( n \), representing the number of cities. The next \( n-1 \) lines each contain two integers, \( u \) and \( v \), representing a road connecting cities \( u \) and \( v \). The last line contains three integers \( a \), \( b \), and \( k \) describing the query.

outputFormat

Output a single line: "Yes" if there exists at least one city \( t \) such that \( \mathrm{dis}(t,a) \oplus \mathrm{dis}(t,b) = k \); otherwise, output "No".

sample

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

No