410486: GYM104025 L Fake Travelling Salesman Problem

The Travelling Salesman Problem (TSP) asks that given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city.

Unfortunately, the TSP is an NP-hard problem. So instead of expecting you to solve it, we propose a Fake Traveling Salesman Problem (FTSP). In FTSP, the map is defined on a $$$n \times m$$$ grids. The salesman starts at $$$(1,1)$$$. He can only move to four adjacent cities each step and can't move out of the grids. He wants to visit each grid exactly once and end up at $$$(x,y)$$$.

Help the salesman find a valid route satisfying such conditions.

The only line contains four integers $$$n,m,x,y\ (2 \leq n,m \leq 500, 1 \leq x \leq n, 1 \leq y \leq m)$$$. It is guaranteed that $$$(x,y) \neq (1,1)$$$.

Output "Yes"(without quotes) or "No"(without quotes) in the first line, represents whether you can find a route.

If the route exists, output $$$n \times m$$$ lines. The $$$i$$$-th line contains two integers $$$a,b$$$, which means the salesman should be in grid $$$a,b$$$ in the $$$i$$$-th step. You should guarantee that:

• $$$a=1,b=1$$$ holds for the first line.
• $$$a=x,b=y$$$ holds for the last line.
• $$$1 \le a \le n, 1 \le b \le m$$$.
• The distance between two adjacent steps is $$$1$$$.

2 2 2 2

No

3 3 2 2

Yes
1 1
2 1
3 1
3 2
3 3
2 3
1 3
1 2
2 2

3 4 3 2

Yes
1 1
1 2
1 3
1 4
2 4
3 4
3 3
2 3
2 2
2 1
3 1
3 2