Ruudukko

warning: unused import: `rand::prelude::*`
 --> input/code.rs:1:5
  |
1 | use rand::prelude::*;
  |     ^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: value assigned to `y` is never read
   --> input/code.rs:215:13
    |
215 |             y += 1;
    |             ^
    |
    = note: `#[warn(unused_assignments)]` on by default
    = help: maybe it is overwritten before being read?

warning: value assigned to `y` is never read
   --> input/code.rs:218:13
    |
218 |             y -= 1;
    |             ^
    |
    = help: maybe it is overwritten before being read?

warning: unused variable: `left`
   --> input/code.rs:412:17
    |
412 |             let left = fill_left(h, x1, y1);
    |                 ^^^^ help: consider prefixing with an underscore: `_left`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `right`
   --> input/code.rs:413:17
    |
413 |             let right = fill_left(h, w + 1 - x2, y2).map(|(y,...

use rand::prelude::*;
use std::collections::HashSet;
use std::io::BufRead;
 
fn flip_y(path: String) -> String {
    path.chars()
        .map(|c| match c {
            'U' => 'D',
            'D' => 'U',
            c => c,
        })
        .collect()
}
 
fn flip_x(path: String) -> String {
    path.chars()
        .map(|c| match c {
            'R' => 'L',
            'L' => 'R',
            c => c,
        })
        .collect()
}
 
fn reverse(path: String) -> String {
    path.chars()
        .rev()
        .map(|c| match c {
            'R' => 'L',
            'L' => 'R',
            'U' => 'D',
            'D' => 'U',
            c => c,
        })
        .collect()
}
 
fn swap_xy(path: String) -> String {
    path.chars()
        .map(|c| match c {
            'R' => 'D',
            'L' => 'U',
            'U' => 'L',
            'D' => 'R',
            c => c,
        })
        .collect()
}
 
fn walk_and_modify<F>(path: String, y1: usize, x1: usize, mut f: F) -> String
where
    F: FnMut(usize, usize, usize, usize) -> Option<String>,
{
    let mut res = "".to_string();
    let mut x = x1;
    let mut y = y1;
    for c in path.chars() {
        let (ny, nx) = match c {
            'U' => (y - 1, x),
            'D' => (y + 1, x),
            'L' => (y, x - 1),
            'R' => (y, x + 1),
            c => panic!("Invalid action '{}'", c),
        };
        let r = f(y, x, ny, nx);
        match r {
            None => res.push(c),
            // Some(s) => res = format!("{}|{}|",res,s),
            Some(s) => res += &s,
        }
 
        x = nx;
        y = ny;
    }
 
    res
}
 
fn brute_solve(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize) -> Option<String> {
    // println!("brute_solve{:?}",(h, w, y1, x1, y2, x2) );
    fn dfs(
        h: usize,
        w: usize,
        y: usize,
        x: usize,
        y2: usize,
        x2: usize,
        d: usize,
        visited: &mut Vec<bool>,
        failing: &mut HashSet<(usize, usize, Vec<bool>)>,
    ) -> Option<String> {
        // println!("{} {} {}",x,y,d);
        if x < 1 || x > w || y < 1 || y > h {
            return None;
        }
        if visited[x - 1 + (y - 1) * w] {
            return None;
        }
        if d == 0 {
            assert!(x == x2 && y == y2);
            return Some("".to_string());
        }
        if x == x2 && y == y2 {
            return None;
        }
        if !failing.insert((x, y, visited.clone())) {
            return None;
        }
        visited[x - 1 + (y - 1) * w] = true;
        if let Some(res) = dfs(h, w, y, x + 1, y2, x2, d - 1, visited, failing) {
            return Some("R".to_string() + &res);
        }
        if let Some(res) = dfs(h, w, y + 1, x, y2, x2, d - 1, visited, failing) {
            return Some("D".to_string() + &res);
        }
        if let Some(res) = dfs(h, w, y, x - 1, y2, x2, d - 1, visited, failing) {
            return Some("L".to_string() + &res);
        }
        if let Some(res) = dfs(h, w, y - 1, x, y2, x2, d - 1, visited, failing) {
            return Some("U".to_string() + &res);
        }
        visited[x - 1 + (y - 1) * w] = false;
        None
    }
 
    dfs(
        h,
        w,
        y1,
        x1,
        y2,
        x2,
        h * w - 1,
        &mut vec![false; h * w],
        &mut HashSet::new(),
    )
}
 
fn solve(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize) -> Option<String> {
    assert!(1 <= x1 && x1 <= w);
    assert!(1 <= x2 && x2 <= w);
    assert!(1 <= y1 && y1 <= h);
    assert!(1 <= y2 && y2 <= h);
 
    if y2 < y1 {
        return solve(h, w, h + 1 - y1, x1, h + 1 - y2, x2).map(flip_y);
    }
    if x2 < x1 {
        return solve(h, w, y1, w + 1 - x1, y2, w + 1 - x2).map(flip_x);
    }
 
    if h == 1 {
        if x1 == 1 && x2 == w {
            Some("R".repeat(w - 1))
        } else {
            None
        }
    } else if h == 2 {
        if y1 == 2 {
            return solve(h, w, h + 1 - y1, x1, h + 1 - y2, x2).map(flip_y);
        }
        assert!(y1 == 1);
 
        if x1 == x2 {
            if x1 == 1 {
                // Go right, down, and then back left
                return Some(format!("{}D{}", "R".repeat(w - 1), "L".repeat(w - 1)));
            } else if x1 == w {
                // Go left, down, and then back right
                return Some(format!("{}D{}", "L".repeat(w - 1), "R".repeat(w - 1)));
            } else {
                return None;
            }
        }
        assert!(x1 < x2);
        // Go first left until the left wall, then back, then fill the space in between, right and back left
        let mut res = "".to_string();
        let mut x = x1;
        while x > 1 {
            res.push('L');
            x -= 1;
        }
        res.push('D');
        while x < x1 {
            res.push('R');
            x += 1;
        }
        // Now we need to go up and down until we reach x2, hopefully on the other side
        let mut y = 2;
        while x + 1 < x2 {
            res.push('R');
            x += 1;
            if y == 1 {
                res.push('D');
                y += 1;
            } else {
                res.push('U');
                y -= 1;
            }
        }
        // In next step we share x coordinate with x2
        res.push('R');
        x += 1;
        if y == y2 {
            // We hit end, this a failure because the other cell in this column is unvisited
            return None;
        }
        // Now we just walk right until wall, go up or down, and then walk back to x2
        while x < w {
            res.push('R');
            x += 1;
        }
        if y == 1 {
            res.push('D');
            y += 1;
        } else {
            res.push('U');
            y -= 1;
        }
        while x > x2 {
            res.push('L');
            x -= 1;
        }
 
        assert!(res.len() == h * w - 1);
        Some(res)
    } else if h == 3 {
        fn fill_left(h: usize, w: usize, y: usize) -> Option<(usize, String)> {
            assert!(h == 3);
            if y == 2 {
                // println!("Reversing");
                // If we have path from (2, w) to (1, w), then we also have the reverse path
                let foo = fill_left(h, w, 1).filter(|(y, _)| *y == 2);
                // println!("{:?}", foo);
                foo.map(|(_, p)| (1, reverse(p)))
            } else if y == 1 {
                let y = if w % 2 == 0 { 2 } else { 3 };
                let res = format!(
                    "{}D{}",
                    "L".repeat(w - 1),
                    solve(2, w, 1, 1, y - 1, w).unwrap()
                );
                Some((y, res))
            } else {
                assert_eq!(y, 3);
                let y = if w % 2 == 0 { 2 } else { 1 };
                let res = format!("{}U{}", "L".repeat(w - 1), solve(2, w, 2, 1, y, w).unwrap());
                Some((y, res))
            }
        }
 
        fn fill_left3(w: usize, y1: usize, y2: usize) -> Option<String> {
            assert!(y1 != y2);
            assert!(w > 0);
            if w == 1 {
                if y1 == 1 && y2 == 3 {
                    Some("DD".to_string())
                } else if y1 == 3 && y2 == 1 {
                    Some("UU".to_string())
                } else {
                    None
                }
            } else {
                if y1 == 1 {
                    if y2 == 2 {
                        fill_left3(w - 1, 1, 3).map(|p| format!("L{}RU", p))
                    } else {
                        assert!(y2 == 3);
                        fill_left3(w - 1, 1, 2).map(|p| format!("L{}RD", p))
                    }
                } else if y1 == 2 {
                    if y2 == 1 {
                        fill_left3(w - 1, 3, 1).map(|p| format!("DL{}R", p))
                    } else {
                        assert!(y2 == 3);
                        fill_left3(w - 1, 1, 3).map(|p| format!("UL{}R", p))
                    }
                } else {
                    assert!(y1 == 3);
                    if y2 == 1 {
                        fill_left3(w - 1, 3, 2).map(|p| format!("L{}RU", p))
                    } else {
                        assert!(y2 == 2);
                        fill_left3(w - 1, 3, 1).map(|p| format!("L{}RD", p))
                    }
                }
            }
        }
        fn fill_right3(w: usize, y1: usize, y2: usize) -> Option<String> {
            fill_left3(w, y1, y2).map(flip_x)
        }
 
        // if w < 3 {
        //     return solve(w, h, x1, y1, x2, y2).map(swap_xy);
        // }
 
        // Brute small cases
        if w <= 4 {
            return brute_solve(h, w, y1, x1, y2, x2);
        }
 
        // If the endpoints are close to each others, brute the local part and then combine with a solution for ends
        if x2 - x1 <= 3 {
            let x1_max_extra = (x1 - 1).min(2);
            let x2_max_extra = (w - x2).min(2);
            for x1_extra in 0..=x1_max_extra {
                for x2_extra in 0..=x2_max_extra {
                    let local_res = brute_solve(
                        3,
                        x2 - x1 + 1 + x1_extra + x2_extra,
                        y1,
                        x1 + 1 - (x1 - x1_extra),
                        y2,
                        x2 + 1 - (x1 - x1_extra),
                    );
                    if let Some(local_res) = local_res {
                        let mut x1_filled = x1 - x1_extra == 1;
                        let mut x2_filled = x2 + x2_extra == w;
                        let local_res = walk_and_modify(local_res, y1, x1, |py1, px1, py2, px2| {
                            if !x1_filled && px1 == x1 - x1_extra && px2 == x1 - x1_extra {
                                // We are at the left edge, try to fill the left side
                                if let Some(p) = fill_left3(x1 - 1 - x1_extra, py1, py2)
                                    .map(|p| format!("L{}R", p))
                                {
                                    x1_filled = true;
                                    Some(p)
                                } else {
                                    None
                                }
                            } else if !x2_filled && px1 == x2 + x2_extra && px2 == x2 + x2_extra {
                                // We are at the right edge, try to fill the right side
                                if let Some(p) = fill_right3(w - x2 - x2_extra, py1, py2)
                                    .map(|p| format!("R{}L", p))
                                {
                                    x2_filled = true;
                                    Some(p)
                                } else {
                                    None
                                }
                            } else {
                                None
                            }
                        });
                        if x1_filled && x2_filled {
                            return Some(local_res);
                        }
                    }
                }
            }
            return None;
        }
 
        // if y1 == 3 {
        //     return solve(h, w, h + 1 - y1, x1, h + 1 - y2, x2).map(flip_y);
        // }
        // assert!(y1 == 1 || y1 == 2);
 
        if x1 != x2 {
            fn combine_middle_part(
                y1: usize,
                x1: usize,
                y2: usize,
                x2: usize,
                left: Option<(usize, String)>,
                right: Option<(usize, String)>,
            ) -> Option<String> {
                assert!(x1 < x2);
                match (left, right) {
                    (Some((ly, lp)), Some((ry, rp))) => {
                        if x1 + 1 == x2 {
                            // They are next to each others, the y coordinates need to match, possibly after a flip
                            if ly == ry {
                                Some(format!("{}R{}", lp, rp))
                            } else if ly == 4 - ry && (y1 == 2 || y2 == 2) {
                                if y1 == 2 {
                                    Some(format!("{}R{}", flip_x(lp), rp))
                                } else {
                                    assert!(y2 == 2);
                                    Some(format!("{}R{}", lp, flip_y(rp)))
                                }
                            } else {
                                None
                            }
                        } else {
                            // Not next to each others
                            if ly == 2 || ry == 2 {
                                None
                            } else {
                                let suffix = if ly == ry { "UUR" } else { "" };
                                let midwidth = if ly == ry { x2 - x1 - 2 } else { x2 - x1 - 1 };
                                if midwidth == 0 {
                                    None
                                } else {
                                    let midres = format!(
                                        "{}D{}D{}{}",
                                        "R".repeat(midwidth),
                                        "L".repeat(midwidth - 1),
                                        "R".repeat(midwidth),
                                        suffix
                                    );
                                    let midres = if ly == 1 { midres } else { flip_y(midres) };
                                    Some(format!("{}{}{}", lp, midres, rp))
                                }
                            }
                        }
                    }
                    _ => None,
                }
            }
 
            // Solve both ends separately, then try to combine them in the middle
            let left = fill_left(h, x1, y1);
            let right = fill_left(h, w + 1 - x2, y2).map(|(y, p)| (y, flip_x(reverse(p))));
            // println!("Left: {:?}", left);
            // println!("Right: {:?}", right);
 
            combine_middle_part(
                y1,
                x1,
                y2,
                x2,
                fill_left(h, x1, y1),
                fill_left(h, w + 1 - x2, y2).map(|(y, p)| (y, flip_x(reverse(p)))),
            )
            .or_else(|| {
                if x1 == 1 && x2 >= 3 {
                    // Try to extend x1 one part to right
                    combine_middle_part(
                        y1,
                        x1 + 1,
                        y2,
                        x2,
                        solve(2, w, 1, y1, 2, 4 - y1).map(|p| (4 - y1, swap_xy(p))),
                        fill_left(h, w + 1 - x2, y2).map(|(y, p)| (y, flip_x(reverse(p)))),
                    )
                } else {
                    None
                }
            })
        // .or_else(|| if x1 == 1 && x2 == 2 {})
        } else {
            // The endpoints are in the same column
            if y1 == 2 || y2 == 2 {
                // One of the endpoints is on the center row
                if w % 2 == 1 {
                    // No solutions with odd number of columns
                    return None;
                }
 
                let rev = y2 != 2;
                let (y1, y2) = if rev { (y2, y1) } else { (y1, y2) };
                let fy = y1 != 1;
                let y1 = 1;
                assert!(y1 == 1);
                assert!(y2 == 2);
 
                let res = if x1 % 2 == 1 {
                    if x1 == 1 {
                        // We are at the left wall, fill the right side
                        Some(format!("R{}LU", flip_x(fill_left(h, w - 1, 1).unwrap().1)))
                    } else {
                        // Flip the board and retry
                        solve(h, w, y1, w + 1 - x1, y2, w + 1 - x2).map(flip_x)
                    }
                } else {
                    // Odd number of columns to the left, go there, then zigzag
                    if x1 == w {
                        Some(format!("L{}RU", fill_left(h, x1 - 1, 1).unwrap().1))
                    } else {
                        Some(format!(
                            "L{}RR{}L",
                            fill_left(h, x1 - 1, 1).unwrap().1,
                            flip_x(fill_left(h, w - x1, 3).unwrap().1)
                        ))
                    }
                };
                let res = if fy { res.map(flip_y) } else { res };
                if rev {
                    res.map(reverse)
                } else {
                    res
                }
            } else {
                let fy = y1 != 1;
                let y1 = 1;
                let y2 = 3;
                let res = if w % 2 == 0 || x1 % 2 != 1 {
                    // Solutions exist only for cases where x divides the width into two even-width parts
                    None
                } else {
                    let left = if x1 == 1 {
                        "D".to_string()
                    } else {
                        format!("L{}R", fill_left(h, x1 - 1, 1).unwrap().1)
                    };
                    let right = if x1 == w {
                        "D".to_string()
                    } else {
                        reverse(format!("R{}L", flip_x(fill_left(h, w - x1, 3).unwrap().1)))
                    };
                    Some(format!("{}{}", left, right))
                };
                if fy {
                    res.map(flip_y)
                } else {
                    res
                }
            }
        }
    } else if h == 4 {
        if (x1 + y1) % 2 == (x2 + y2) % 2 {
            return None;
        }
        fn fill_left4(w: usize, y1: usize, y2: usize) -> Option<String> {
            if y1 > y2 {
                return fill_left4(w, 5 - y1, 5 - y2).map(flip_y);
            }
            if y1 == y2 {
                return None;
            }
            assert!(y1 != y2);
            assert!(w > 0);
            if w == 1 {
                if y1 == 1 && y2 == 4 {
                    Some("DDD".to_string())
                } else if y1 == 4 && y2 == 1 {
                    Some("UUU".to_string())
                } else {
                    None
                }
            } else {
                let l = "L".repeat(w - 2);
                let r = "R".repeat(w - 2);
                if y1 == 1 {
                    if y2 == 2 {
                        Some(format!("L{}D{}D{}D{}RUU", l, r, l, r))
                    } else if y2 == 4 {
                        Some(format!("L{}D{}RDL{}D{}R", l, r, l, r))
                    } else {
                        None
                    }
                } else if y1 == 2 {
                    if y2 == 3 {
                        Some(format!("UL{}D{}D{}D{}RU", l, r, l, r))
                    } else {
                        None
                    }
                } else {
                    assert!(y1 == 3);
                    assert!(y2 == 4);
                    Some(format!("UUL{}D{}D{}D{}R", l, r, l, r))
                }
            }
        }
        fn fill_right4(w: usize, y1: usize, y2: usize) -> Option<String> {
            fill_left4(w, y1, y2).map(flip_x)
        }
 
        if x2 - x1 <= 3 {
            let x1_max_extra = (x1 - 1).min(2);
            let x2_max_extra = (w - x2).min(2);
            for x1_extra in 0..=x1_max_extra {
                for x2_extra in 0..=x2_max_extra {
                    let local_res = brute_solve(
                        4,
                        x2 - x1 + 1 + x1_extra + x2_extra,
                        y1,
                        x1 + 1 - (x1 - x1_extra),
                        y2,
                        x2 + 1 - (x1 - x1_extra),
                    );
                    // println!("{:?}", local_res);
                    let mut x1_filled = x1 == 1;
                    let mut x2_filled = x2 == w;
                    if let Some(local_res) = local_res {
                        let mut x1_filled = x1 - x1_extra == 1;
                        let mut x2_filled = x2 + x2_extra == w;
                        let local_res = walk_and_modify(local_res, y1, x1, |py1, px1, py2, px2| {
                            if !x1_filled && px1 == x1 - x1_extra && px2 == x1 - x1_extra {
                                // We are at the left edge, try to fill the left side
                                if let Some(p) = fill_left4(x1 - 1 - x1_extra, py1, py2)
                                    .map(|p| format!("L{}R", p))
                                {
                                    x1_filled = true;
                                    Some(p)
                                } else {
                                    None
                                }
                            } else if !x2_filled && px1 == x2 + x2_extra && px2 == x2 + x2_extra {
                                // We are at the right edge, try to fill the right side
                                if let Some(p) = fill_right4(w - x2 - x2_extra, py1, py2)
                                    .map(|p| format!("R{}L", p))
                                {
                                    x2_filled = true;
                                    Some(p)
                                } else {
                                    None
                                }
                            } else {
                                None
                            }
                        });
                        if x1_filled && x2_filled {
                            return Some(local_res);
                        }
                    }
                }
            }
            return None;
        }
 
        let (x1, left) = if x1 == 1 {
            if y1 == 1 {
                (1, (4, "DDD".to_string()))
            } else if y1 == 2 {
                (2, (4, "URDDLDR".to_string()))
            } else if y1 == 3 {
                (2, (1, "DRUULUR".to_string()))
            } else {
                (1, (1, "UUU".to_string()))
            }
        } else {
            (
                x1,
                fill_left4(x1, y1, 1)
                    .map(|p| (1, p))
                    .or(fill_left4(x1, y1, 4).map(|p| (4, p)))
                    .unwrap(),
            )
        };
        let (x2, right) = if x2 == w {
            if y2 == 1 {
                (w, (4, "UUU".to_string()))
            } else if y2 == 2 {
                (w - 1, (4, "RULUURD".to_string()))
            } else if y2 == 3 {
                (w - 1, (1, "RDLDDRU".to_string()))
            } else {
                (w, (1, "DDD".to_string()))
            }
        } else {
            (
                x2,
                fill_right4(w + 1 - x2, y2, 1)
                    .map(reverse)
                    .map(|p| (1, p))
                    .or(fill_right4(w + 1 - x2, y2, 4).map(reverse).map(|p| (4, p)))
                    .unwrap(),
            )
        };
 
        let mut res = left.1;
        let mut y1 = left.0;
        let mut x1 = x1;
        while x1 + 1 < x2 {
            if y1 == 1 {
                res += "RDDD";
            } else {
                res += "RUUU";
            }
            y1 = 5 - y1;
            x1 += 1;
        }
        assert!(y1 == right.0);
        res += "R";
        res += &right.1;
        Some(res)
    } else {
        unimplemented!()
    }
}
 
fn main() {
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let mut lines = stdin.lines();
 
    let t: usize = lines.next().unwrap().unwrap().parse().unwrap();
    for _ in 0..t {
        let input: Vec<usize> = lines
            .next()
            .unwrap()
            .unwrap()
            .split_whitespace()
            .map(|v| v.parse().unwrap())
            .collect();
        if let Some(res) = solve(input[0], input[1], input[2], input[3], input[4], input[5]) {
            println!("YES");
            println!("{}", res);
        } else {
            println!("NO");
        }
    }
}
 
#[cfg(test)]
mod tests {
    use super::*;
 
    fn assert_solution(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize, path: &str) {
        println!("{}", path);
        let mut visited = vec![false; h * w];
        let mut x = x1;
        let mut y = y1;
        visited[(x - 1) + (y - 1) * w] = true;
        for c in path.chars() {
            match c {
                'U' => y -= 1,
                'D' => y += 1,
                'L' => x -= 1,
                'R' => x += 1,
                c => panic!("Invalid action '{}'", c),
            }
            assert!(
                x >= 1 && x <= w && y >= 1 && y <= h,
                "Solution {} walked out of bounds",
                path
            );
            assert!(
                !visited[(x - 1) + (y - 1) * w],
                "Solution {} has already visited cell {}, {}",
                path,
                y,
                x
            );
            visited[(x - 1) + (y - 1) * w] = true;
        }
        assert!(
            visited.into_iter().all(std::convert::identity),
            "Solution {} didn't visit all cells",
            path
        );
        assert!((x, y) == (x2, y2));
    }
 
    fn assert_solvable(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize) {
        assert_solution(h, w, y1, x1, y2, x2, &solve(h, w, y1, x1, y2, x2).unwrap());
    }
 
    fn assert_solvable_perm(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize) {
        assert_solvable(h, w, y1, x1, y2, x2);
        assert_solvable(h, w, y2, x2, y1, x1);
        assert_solvable(w, h, x1, y1, x2, y2);
        assert_solvable(w, h, x2, y2, x1, y1);
 
        assert_solvable(h, w, h + 1 - y1, x1, h + 1 - y2, x2);
        assert_solvable(h, w, h + 1 - y2, x2, h + 1 - y1, x1);
        assert_solvable(w, h, w + 1 - x1, y1, w + 1 - x2, y2);
        assert_solvable(w, h, w + 1 - x2, y2, w + 1 - x1, y1);
 
        assert_solvable(h, w, y1, w + 1 - x1, y2, w + 1 - x2);
        assert_solvable(h, w, y2, w + 1 - x2, y1, w + 1 - x1);
        assert_solvable(w, h, x1, h + 1 - y1, x2, h + 1 - y2);
        assert_solvable(w, h, x2, h + 1 - y2, x1, h + 1 - y1);
 
        assert_solvable(h, w, h + 1 - y1, w + 1 - x1, h + 1 - y2, w + 1 - x2);
        assert_solvable(h, w, h + 1 - y2, w + 1 - x2, h + 1 - y1, w + 1 - x1);
        assert_solvable(w, h, w + 1 - x1, h + 1 - y1, w + 1 - x2, h + 1 - y2);
        assert_solvable(w, h, w + 1 - x2, h + 1 - y2, w + 1 - x1, h + 1 - y1);
    }
 
    fn assert_unsolvable(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize) {
        assert!(solve(h, w, y1, x1, y2, x2).is_none());
    }
 
    fn assert_unsolvable_perm(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize) {
        assert_unsolvable(h, w, y1, x1, y2, x2);
        assert_unsolvable(h, w, y2, x2, y1, x1);
        assert_unsolvable(w, h, x1, y1, x2, y2);
        assert_unsolvable(w, h, x2, y2, x1, y1);
 
        assert_unsolvable(h, w, h + 1 - y1, x1, h + 1 - y2, x2);
        assert_unsolvable(h, w, h + 1 - y2, x2, h + 1 - y1, x1);
        assert_unsolvable(w, h, w + 1 - x1, y1, w + 1 - x2, y2);
        assert_unsolvable(w, h, w + 1 - x2, y2, w + 1 - x1, y1);
 
        assert_unsolvable(h, w, y1, w + 1 - x1, y2, w + 1 - x2);
        assert_unsolvable(h, w, y2, w + 1 - x2, y1, w + 1 - x1);
        assert_unsolvable(w, h, x1, h + 1 - y1, x2, h + 1 - y2);
        assert_unsolvable(w, h, x2, h + 1 - y2, x1, h + 1 - y1);
 
        assert_unsolvable(h, w, h + 1 - y1, w + 1 - x1, h + 1 - y2, w + 1 - x2);
        assert_unsolvable(h, w, h + 1 - y2, w + 1 - x2, h + 1 - y1, w + 1 - x1);
        assert_unsolvable(w, h, w + 1 - x1, h + 1 - y1, w + 1 - x2, h + 1 - y2);
        assert_unsolvable(w, h, w + 1 - x2, h + 1 - y2, w + 1 - x1, h + 1 - y1);
    }
 
    #[test]
    fn test_solve1() {
        assert_solvable(1, 3, 1, 1, 1, 3);
        assert_solvable(1, 3, 1, 3, 1, 1);
        assert_unsolvable(1, 3, 1, 2, 1, 3);
    }
 
    #[test]
    fn test_solve2() {
        assert_unsolvable(2, 2, 1, 1, 2, 2);
        assert_solvable(2, 2, 1, 1, 2, 1);
 
        assert_solvable(2, 3, 1, 1, 2, 3);
        assert_unsolvable(2, 3, 1, 1, 1, 3);
    }
 
    #[test]
    fn foo() {
        assert_solvable(4, 5, 1, 1, 2, 5);
        panic!()
        // assert_solvable(3,20, 1, 1, 2, 1);
        // assert_solvable_perm(3, 3, 1, 1, 2, 2);
    }
 
    #[test]
    fn test_solve3() {
        assert_solvable(3, 3, 1, 1, 3, 3);
        assert_solvable(3, 4, 1, 2, 1, 3);
        assert_solvable(3, 4, 1, 2, 3, 3);
        assert_unsolvable(3, 3, 1, 2, 1, 3);
 
        // Width 1
        assert_solvable_perm(3, 1, 1, 1, 3, 1);
        assert_solvable_perm(3, 1, 3, 1, 1, 1);
        assert_unsolvable_perm(3, 1, 1, 1, 2, 1);
        assert_unsolvable_perm(3, 1, 3, 1, 2, 1);
        assert_unsolvable_perm(3, 1, 2, 1, 1, 1);
        assert_unsolvable_perm(3, 1, 2, 1, 3, 1);
 
        // Width 2
        assert_solvable_perm(3, 2, 1, 1, 1, 2);
        assert_solvable_perm(3, 2, 1, 1, 2, 1);
        assert_solvable_perm(3, 2, 1, 1, 3, 2);
        assert_unsolvable_perm(3, 2, 1, 1, 2, 2);
        assert_unsolvable_perm(3, 2, 1, 1, 3, 1);
 
        // Width 3
        assert_solvable_perm(3, 3, 1, 1, 2, 2);
        assert_solvable_perm(3, 3, 1, 1, 3, 3);
        assert_solvable_perm(3, 3, 1, 1, 3, 1);
        assert_solvable_perm(3, 3, 1, 1, 1, 3);
        for y in 1..=3 {
            for x in 1..=3 {
                if x != 2 || y != 1 {
                    assert_unsolvable_perm(3, 3, 1, 2, y, x);
                }
            }
        }
 
        // assert_solvable(3, 2, 3, 1, 1, 1);
 
        // Wider
        for x in 1..=6 {
            assert_solvable(3, 6, 1, x, 2, x);
            assert_solvable(3, 6, 2, x, 1, x);
            assert_solvable(3, 6, 2, x, 3, x);
            assert_solvable(3, 6, 3, x, 2, x);
        }
 
        for x in 1..=7 {
            if x % 2 == 1 {
                assert_solvable(3, 7, 1, x, 3, x);
                assert_solvable(3, 7, 3, x, 1, x);
            } else {
                assert_unsolvable(3, 7, 1, x, 3, x);
                assert_unsolvable(3, 7, 3, x, 1, x);
            }
        }
 
        // Other manual samples
        assert_solvable(3, 6, 3, 2, 3, 3);
        assert_solvable(3, 6, 1, 2, 1, 3);
        assert_unsolvable(3, 6, 1, 2, 1, 4);
        assert_unsolvable(3, 6, 1, 2, 1, 5);
        assert_unsolvable(3, 6, 1, 2, 1, 6);
 
        assert_solvable(3, 6, 1, 3, 1, 4);
        assert_unsolvable(3, 6, 1, 3, 1, 5);
        assert_solvable(3, 6, 1, 3, 1, 6);
 
        assert_solvable(3, 6, 1, 4, 1, 5);
        assert_unsolvable(3, 6, 1, 4, 1, 6);
 
        assert_solvable(3, 6, 1, 5, 1, 6);
    }
 
    #[test]
    fn test_solve4() {
        assert_solvable(4, 4, 1, 1, 1, 2);
    }
 
    #[test]
    fn test_against_brute() {
        for w in 1..=6 {
            for h in 4..=4 {
                for x1 in 1..=w {
                    for y1 in 1..=h {
                        for x2 in 1..=w {
                            for y2 in 1..=h {
                                if x1 != x2 || y1 != y2 {
                                    println!("Testing {:?}", (h, w, y1, x1, y2, x2));
                                    let br = brute_solve(h, w, y1, x1, y2, x2);
                                    let sr = solve(h, w, y1, x1, y2, x2);
                                    if br.is_some() {
                                        assert!(sr.is_some(), "Brute found solution for instance {:?}, but solve didn't", (h, w, y1, x1, y2, x2));
                                        assert_solution(h, w, y1, x1, y2, x2, &sr.unwrap());
                                        assert_solution(h, w, y1, x1, y2, x2, &br.unwrap());
                                    } else {
                                        assert!(sr.is_none(), "Brute didn't find a solution for instance {:?}, but solve did with {}", (h, w, y1, x1, y2, x2), sr.unwrap());
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}