XOR Distance Query on a Tree

In a country with n cities and n-1 roads, the cities form a tree. Given two specific 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\)

Here, \(\mathrm{dis}_{x, y}\) denotes the distance (number of edges) between city \(x\) and city \(y\) in the tree, and \(\oplus\) is the bitwise XOR operator.

You are given the structure of the tree and the values for a, b, and k. Determine if there exists at least one city t satisfying the above condition.

inputFormat

The first line contains four integers n, a, b and k where:

• n (\(2 \leq n \leq 10^5\)) is the number of cities.
• a and b (1-indexed) are the two given cities.
• k is the target XOR value.

Then follow n-1 lines, each containing two integers u and v, denoting a bidirectional road between cities u and v.

outputFormat

If there exists at least one city t such that \(\mathrm{dis}_{t, a} \oplus \mathrm{dis}_{t, b} = k\), print YES. Otherwise, print NO.

sample

3 1 3 2
1 2
2 3

YES