406901: GYM102606 H Heat Pipes

Cuber QQ is opening a vegetable base in ECNU, providing fresh fruits and vegetables during the lockdown and in case of future emergencies. The vegetable base has many greenhouses. Some of them are connected with heat pipes. Each greenhouse has a temperature controlling system, that can tune the air temperature within the greenhouse.

The ECNUers are picky eating for vegetables. As different people might have different appetites, Cuber QQ has to plant all kinds of vegetables in his base to satisfy their needs. Each vegetable, has a best temperature, under which it will be thriving. As a perfectionist, Cuber QQ won't allow any vegetable to grow in a greenhouse with an imperfect air temperature.

As the seeds of plants haven't arrived yet, Cuber QQ needs to prepare for all possibilities. He assumes that all the best temperatures are between $$$a$$$ degrees centigrade and $$$b$$$. This means, at least one greenhouse should be tuned to temperature $$$t$$$ for all integers $$$t$$$ between $$$a$$$ and $$$b$$$, inclusively. Obviously, if he has at least $$$b-a+1$$$ greenhouses and he assigns a specific temperature to each greenhouse, he should be able to do that.

However, the heat pipes between the greenhouses are making everything difficult. The heat pipes do save energy by sharing heats, but at the same time, they impose constraints that if two greenhouses are connected with a pipe, the difference of their temperature should be exactly one degrees centigrade. Believe it or not, engineers have put many efforts into maintaining this balance and seeking for the best trade-off between efficiency and controlling precision, but it has been many years since they have built this, and no one knows what they were thinking about when they built this.

Now all we care about is to solve our problem: whether it is possible to assign temperatures to greenhouses that cover all integers from $$$a$$$ to $$$b$$$ and satisfy the constraints of heat pipes. Also note that, please do not assign a temperature outside this interval as it would be a complete waste and not acceptable.

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$).

The first line of each test case contains four space-separated integers $$$n$$$, $$$m$$$, $$$a$$$ and $$$b$$$ ($$$1 \le n \le 2~000$$$, $$$0 \le m\le 50~000$$$, $$$0 \le a \le b \le n$$$), the number of greenhouses, the number of heat pipes, and the temperature interval, respectively.

The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1\le u_i,v_i \le n$$$, $$$u_i \ne v_i$$$), which is the $$$i$$$-th heat pipe.

It is guaranteed that there is at most one heat pipe between two greenhouses. The sum of $$$n$$$ over all test cases does not exceed $$$2~000$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$50~000$$$ .

For each test case:

• If there is no solution, print "No" (without quotes) in a single line.
• Otherwise, print "Yes" (without quotes) in the first line, and the second line contains $$$n$$$ space-separated integers $$$x_1, x_2, \ldots, x_n$$$ ($$$a \le x_i \le b$$$), where $$$x_i$$$ is the temperature you want to tune the $$$i$$$-th greenhouse to.
• If there are multiple answers, print any of them.

You can output "Yes" or "No" in any cases.

2
3 3 1 2
1 2
2 3
3 1
3 2 1 2
1 2
2 3

No
Yes
1 2 1