tests/graph6.rs

use petgraph::{
    csr::Csr,
    graph6::{from_graph6_representation, get_graph6_representation, FromGraph6, ToGraph6},
    Graph, Undirected,
};

#[cfg(feature = "graphmap")]
use petgraph::graphmap::GraphMap;

#[cfg(feature = "matrix_graph")]
use petgraph::matrix_graph::UnMatrix;

#[cfg(feature = "stable_graph")]
use petgraph::stable_graph::StableGraph;

#[test]
fn generic_graph6_encoder_test_cases() {
    for (order, graph6_str, edges) in TEST_CASES {
        test_generic_graph6_encoder(graph6_str, order, edges.to_vec());
    }
}

fn test_generic_graph6_encoder(expected_graph6_str: &str, order: usize, edges: Vec<(u16, u16)>) {
    type G = Graph<(), (), Undirected, u16>;

    // Assert encoded graph6 string is as expected
    let mut graph: G = Graph::with_capacity(order, edges.len());
    for _ in 0..order {
        graph.add_node(());
    }
    graph.extend_with_edges(edges);

    let graph6_string = get_graph6_representation(&graph);
    assert_eq!(graph6_string, expected_graph6_str);
}

#[test]
fn graph6_generic_decoder_test_cases() {
    for (order, graph6_str, edges) in TEST_CASES {
        test_graph6_generic_decoder(graph6_str, order, edges.to_vec());
    }
}

fn test_graph6_generic_decoder(
    graph6_str: &str,
    expected_order: usize,
    mut expected_edges: Vec<(u16, u16)>,
) {
    type G = (usize, Vec<(u16, u16)>);

    let (order, mut edges): G = from_graph6_representation(graph6_str.to_string());
    assert_eq!(order, expected_order, "order should be the same");

    edges.sort();
    expected_edges.sort();
    assert_eq!(edges, expected_edges, "edges should be the same");
}

#[test]
fn graph6_for_graph_test_cases() {
    for (order, graph6_str, edges) in TEST_CASES {
        test_graph6_for_graph(graph6_str, order, edges.to_vec());
    }
}

fn test_graph6_for_graph(graph6_str: &str, order: usize, edges: Vec<(u16, u16)>) {
    type G = Graph<(), (), Undirected, u16>;
    let size = edges.len();

    // Build test graph
    let mut graph: G = Graph::with_capacity(order, size);
    for _ in 0..order {
        graph.add_node(());
    }
    graph.extend_with_edges(edges);

    // Assert encoded graph6 string is as expected
    let graph6_string = graph.graph6_string();
    assert_eq!(graph6_string, graph6_str);

    // Assert decoded graph properties
    let decoded_graph = G::from_graph6_string(graph6_string);
    assert_eq!(decoded_graph.node_count(), order);
    assert_eq!(decoded_graph.edge_count(), size);

    // Assert re-encoded graph6 string is the same
    assert_eq!(decoded_graph.graph6_string(), graph6_str);
}

#[cfg(feature = "stable_graph")]
#[test]
fn graph6_for_stable_graph_test_cases() {
    for (order, graph6_str, edges) in TEST_CASES {
        test_graph6_for_stable_graph(graph6_str, order, edges.to_vec());
    }
}

#[cfg(feature = "stable_graph")]
fn test_graph6_for_stable_graph(graph6_str: &str, order: usize, edges: Vec<(u16, u16)>) {
    type G = StableGraph<(), (), Undirected, u16>;
    let size = edges.len();

    // Build test graph
    let mut graph = G::with_capacity(order, edges.len());
    for _ in 0..order {
        graph.add_node(());
    }
    graph.extend_with_edges(edges);

    // Assert encoded graph6 string is as expected
    let graph6_string = graph.graph6_string();
    assert_eq!(graph6_string, graph6_str);

    // Assert decoded graph properties
    let decoded_graph = G::from_graph6_string(graph6_string);
    assert_eq!(decoded_graph.node_count(), order);
    assert_eq!(decoded_graph.edge_count(), size);

    // Assert re-encoded graph6 string is the same
    assert_eq!(decoded_graph.graph6_string(), graph6_str);
}

#[cfg(feature = "graphmap")]
#[test]
fn graph6_for_graph_map_test_cases() {
    for (order, graph6_str, edges) in TEST_CASES {
        test_graph6_for_graph_map(graph6_str, order, edges.to_vec());
    }
}

#[cfg(feature = "graphmap")]
fn test_graph6_for_graph_map(graph6_str: &str, order: usize, edges: Vec<(u16, u16)>) {
    type G = GraphMap<u16, (), Undirected>;
    let size = edges.len();

    // Build test graph
    let mut graph = G::with_capacity(order, edges.len());
    for i in 0..order {
        graph.add_node(i as u16);
    }
    for (a, b) in edges {
        graph.add_edge(a, b, ());
    }

    // Assert encoded graph6 string is as expected
    let graph6_string = graph.graph6_string();
    assert_eq!(graph6_string, graph6_str);

    // Assert decoded graph properties
    let decoded_graph = G::from_graph6_string(graph6_string);
    assert_eq!(decoded_graph.node_count(), order);
    assert_eq!(decoded_graph.edge_count(), size);

    // Assert re-encoded graph6 string is the same
    assert_eq!(decoded_graph.graph6_string(), graph6_str);
}

#[cfg(feature = "matrix_graph")]
#[test]
fn graph6_for_matrix_graph_test_cases() {
    for (order, graph6_str, edges) in TEST_CASES {
        test_graph6_for_matrix_graph(graph6_str, order, edges.to_vec());
    }
}

#[cfg(feature = "matrix_graph")]
fn test_graph6_for_matrix_graph(graph6_str: &str, order: usize, edges: Vec<(u16, u16)>) {
    type G = UnMatrix<(), ()>;
    let size = edges.len();

    // Build test graph
    let mut graph = G::with_capacity(order);
    for _ in 0..order {
        graph.add_node(());
    }
    graph.extend_with_edges(edges.iter());

    // Assert encoded graph6 string is as expected
    let graph6_string = graph.graph6_string();
    assert_eq!(graph6_string, graph6_str);

    // Assert decoded graph properties
    let decoded_graph = G::from_graph6_string(graph6_string);
    assert_eq!(decoded_graph.node_count(), order);
    assert_eq!(decoded_graph.edge_count(), size);

    // Assert re-encoded graph6 string is the same
    assert_eq!(decoded_graph.graph6_string(), graph6_str);
}

#[test]
fn graph6_for_csr_test_cases() {
    for (order, graph6_str, edges) in TEST_CASES {
        test_graph6_for_csr(graph6_str, order, edges.to_vec());
    }
}

fn test_graph6_for_csr(graph6_str: &str, order: usize, edges: Vec<(u16, u16)>) {
    type G = Csr<(), (), Undirected, u16>;
    let size = edges.len();

    // Build test graph
    let mut graph = G::new();
    let mut nodes = Vec::new();
    for _ in 0..order {
        let i = graph.add_node(());
        nodes.push(i);
    }
    for (a, b) in edges {
        graph.add_edge(a, b, ());
    }

    // Assert encoded graph6 string is as expected
    let graph6_string = graph.graph6_string();
    assert_eq!(graph6_string, graph6_str);

    // Assert decoded graph properties
    let decoded_graph = G::from_graph6_string(graph6_string);
    assert_eq!(decoded_graph.node_count(), order);
    assert_eq!(decoded_graph.edge_count(), size);

    // Assert re-encoded graph6 string is the same
    assert_eq!(decoded_graph.graph6_string(), graph6_str);
}

// Test cases format: (graph order, expected ghaph6 representation, graph edges)
#[allow(clippy::type_complexity)]
#[rustfmt::skip]
const TEST_CASES: [(usize, &str, &[(u16, u16)]); 20] = [
    // Empty Graphs
    (0, r"?", &[]),
    (1, r"@", &[]),
    (2, r"A?", &[]),
    // Small Graphs
    (5, r"DQc", &[(0, 2), (0, 4), (1, 3), (3, 4)]),
    (5, r"Dhc", &[(0, 1), (0, 4), (1, 2), (2, 3), (3, 4)]),
    (5, r"D^k", &[(0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
    (6, r"E@??", &[(2, 3)]),
    (6, r"Ej]o", &[(0, 1), (0, 5), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5)]),
    (9, r"H?O??_k", &[(1, 4), (2, 8), (3, 7), (4, 8), (5, 8)]),
    (10, r"IrGoS@?o_", &[(0, 1), (0, 2), (0, 7), (0, 9), (1, 3), (1, 8), (1, 9), (2, 3), (2, 4), (2, 5), (3, 5), (4, 6), (6, 9)]),
    (10, r"I~~~~~~~w", &[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (5, 6), (5, 7), (5, 8), (5, 9), (6, 7), (6, 8), (6, 9), (7, 8), (7, 9), (8, 9)]),
    (11, r"Jsa@IchDIS_", &[(6, 10), (9, 10), (6, 7), (7, 8), (8, 9), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 10), (1, 7), (2, 6), (2, 8), (3, 7), (3, 9), (4, 10), (4, 8), (5, 6), (5, 9)]),
    // Complete Graphs
    (2, r"A_", &[(0, 1)]),
    (3, r"Bw", &[(0, 1), (0, 2), (1, 2)]),
    (5, r"D~{", &[(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]),
    (7, r"F~~~w", &[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)]),
    // Petersen
    (10, r"IheA@GUAo", &[(0, 1), (0, 4), (0, 5), (1, 2), (1, 6), (2, 3), (2, 7), (3, 4), (3, 8), (4, 9), (5, 7), (5, 8), (6, 8), (6, 9), (7, 9)]),
    // Flower
    (
        20, r"ShCGHC@?GGg@?@?Gp?K??C?CA?G?_G?Cc",
        &[(0, 1), (0, 14), (0, 15), (1, 2), (1, 11), (2, 3), (2, 7), (3, 16), (3, 4), (4, 5), (4, 14), (5, 6), (5, 10), (6, 17), (6, 7), (7, 8), (8, 9), (8, 13), (9, 18), (9, 10), (10, 11), (11, 12), (12, 19), (12, 13), (13, 14), (15, 16), (15, 19), (16, 17), (17, 18), (18, 19)],
    ),
    // Corner Case: order = 62
    (
        62, r"}x@?xx|G[RO{QRDDMWAJ@XAT\M@IBsP?P[jJKOECP_QKSsL@_Th?mUp@@WC_woIl_nI?AF_ISAGNGxe?pikrJVOwWEqoMKhWGAjk[XPn?WUGrWC]jUjwPJLF@?OU?IGSoqT_rpEM[KCpTvGYBgRvOyJ`\adaY?qsESfR{IQWs?mT}bB@[|?p}MOCOEUZKMw]xKeV[en_EK{eBN?Add?H_@GeE_Bo@?_?PmabQuWc?FHVWcwCLWUF]l??WdIOtyePOc`Sb{SGCU[[__b[OiWnDeCXB@CwW@q_GAYY^eWD[tmoPDf{W]eKjzWCCKOj_",
        &[(0, 32), (0, 1), (0, 49), (0, 2), (0, 35), (0, 19), (0, 52), (0, 37), (0, 22), (0, 54), (0, 40), (0, 10), (0, 58), (0, 11), (0, 59), (0, 44), (0, 28), (0, 61), (0, 29), (0, 31), (1, 32), (1, 16), (1, 17), (1, 2), (1, 50), (1, 35), (1, 36), (1, 20), (1, 5), (1, 38), (1, 23), (1, 8), (1, 57), (1, 42), (1, 60), (1, 12), (1, 45), (1, 30), (1, 14), (1, 46), (1, 31), (1, 15), (1, 47), (2, 16), (2, 48), (2, 34), (2, 18), (2, 50), (2, 3), (2, 35), (2, 51), (2, 37), (2, 21), (2, 53), (2, 38), (2, 7), (2, 23), (2, 8), (2, 56), (2, 9), (2, 57), (2, 42), (2, 58), (2, 43), (2, 60), (2, 44), (2, 14), (2, 46), (2, 47), (3, 48), (3, 33), (3, 17), (3, 49), (3, 50), (3, 36), (3, 20), (3, 21), (3, 6), (3, 7), (3, 55), (3, 8), (3, 57), (3, 42), (3, 58), (3, 27), (3, 59), (3, 60), (3, 44), (3, 61), (3, 13), (3, 14), (3, 47), (4, 32), (4, 48), (4, 33), (4, 17), (4, 49), (4, 34), (4, 50), (4, 19), (4, 36), (4, 20), (4, 37), (4, 6), (4, 38), (4, 22), (4, 7), (4, 8), (4, 10), (4, 26), (4, 43), (4, 27), (4, 12), (4, 61), (4, 45), (5, 16), (5, 17), (5, 34), (5, 18), (5, 51), (5, 20), (5, 37), (5, 53), (5, 6), (5, 54), (5, 7), (5, 39), (5, 8), (5, 24), (5, 41), (5, 42), (5, 11), (5, 43), (5, 27), (5, 59), (5, 44), (5, 13), (5, 29), (5, 30), (5, 15), (6, 32), (6, 48), (6, 33), (6, 49), (6, 35), (6, 54), (6, 23), (6, 55), (6, 40), (6, 24), (6, 25), (6, 57), (6, 58), (6, 11), (6, 43), (6, 60), (6, 28), (6, 29), (6, 14), (6, 47), (7, 32), (7, 48), (7, 33), (7, 17), (7, 18), (7, 35), (7, 37), (7, 21), (7, 39), (7, 8), (7, 40), (7, 56), (7, 9), (7, 10), (7, 58), (7, 11), (7, 60), (7, 12), (7, 45), (7, 29), (7, 14), (7, 46), (7, 15), (8, 48), (8, 49), (8, 19), (8, 36), (8, 20), (8, 38), (8, 22), (8, 54), (8, 23), (8, 55), (8, 9), (8, 41), (8, 25), (8, 10), (8, 11), (8, 43), (8, 28), (8, 61), (8, 45), (8, 29), (8, 46), (8, 15), (9, 32), (9, 49), (9, 51), (9, 37), (9, 38), (9, 22), (9, 56), (9, 41), (9, 25), (9, 43), (9, 27), (9, 60), (9, 28), (9, 61), (9, 13), (9, 31), (10, 16), (10, 33), (10, 17), (10, 49), (10, 35), (10, 20), (10, 37), (10, 38), (10, 54), (10, 40), (10, 25), (10, 42), (10, 26), (10, 27), (10, 12), (10, 28), (10, 31), (11, 32), (11, 17), (11, 49), (11, 34), (11, 54), (11, 39), (11, 23), (11, 55), (11, 40), (11, 56), (11, 60), (11, 12), (11, 44), (11, 28), (11, 13), (11, 30), (12, 32), (12, 33), (12, 17), (12, 49), (12, 35), (12, 51), (12, 36), (12, 20), (12, 37), (12, 23), (12, 40), (12, 57), (12, 26), (12, 58), (12, 60), (12, 44), (12, 61), (12, 45), (12, 30), (13, 32), (13, 16), (13, 48), (13, 33), (13, 18), (13, 51), (13, 36), (13, 20), (13, 52), (13, 55), (13, 40), (13, 24), (13, 41), (13, 25), (13, 42), (13, 26), (13, 43), (13, 59), (13, 45), (13, 30), (14, 48), (14, 18), (14, 37), (14, 23), (14, 56), (14, 42), (14, 60), (14, 28), (14, 61), (14, 30), (14, 46), (14, 31), (14, 15), (14, 47), (15, 32), (15, 16), (15, 48), (15, 18), (15, 50), (15, 21), (15, 24), (15, 41), (15, 25), (15, 42), (15, 43), (15, 60), (15, 44), (15, 45), (15, 31), (16, 48), (16, 18), (16, 35), (16, 19), (16, 36), (16, 20), (16, 37), (16, 21), (16, 38), (16, 22), (16, 54), (16, 39), (16, 55), (16, 25), (16, 42), (16, 58), (16, 60), (16, 28), (16, 61), (16, 29), (16, 46), (17, 50), (17, 35), (17, 36), (17, 52), (17, 37), (17, 53), (17, 40), (17, 24), (17, 41), (17, 58), (17, 27), (17, 44), (17, 61), (17, 30), (17, 46), (17, 31), (18, 48), (18, 51), (18, 20), (18, 52), (18, 37), (18, 53), (18, 54), (18, 39), (18, 24), (18, 56), (18, 25), (18, 57), (18, 42), (18, 43), (18, 60), (18, 61), (18, 29), (18, 46), (18, 47), (19, 48), (19, 34), (19, 35), (19, 51), (19, 36), (19, 20), (19, 37), (19, 53), (19, 22), (19, 54), (19, 23), (19, 56), (19, 41), (19, 25), (19, 42), (19, 27), (19, 60), (19, 61), (19, 31), (20, 32), (20, 48), (20, 33), (20, 50), (20, 35), (20, 36), (20, 52), (20, 37), (20, 23), (20, 24), (20, 56), (20, 41), (20, 42), (20, 26), (20, 58), (20, 43), (20, 44), (20, 61), (21, 32), (21, 33), (21, 49), (21, 34), (21, 35), (21, 51), (21, 52), (21, 39), (21, 55), (21, 40), (21, 56), (21, 41), (21, 43), (21, 27), (21, 59), (21, 29), (21, 30), (21, 46), (21, 31), (22, 32), (22, 33), (22, 49), (22, 50), (22, 35), (22, 52), (22, 53), (22, 39), (22, 23), (22, 55), (22, 40), (22, 56), (22, 57), (22, 42), (22, 61), (22, 30), (22, 46), (23, 48), (23, 34), (23, 50), (23, 24), (23, 56), (23, 41), (23, 25), (23, 57), (23, 26), (23, 27), (23, 44), (23, 61), (23, 29), (23, 30), (23, 46), (23, 31), (24, 52), (24, 38), (24, 54), (24, 55), (24, 41), (24, 27), (24, 59), (24, 44), (24, 45), (24, 46), (24, 31), (25, 34), (25, 37), (25, 53), (25, 54), (25, 41), (25, 57), (25, 58), (25, 43), (25, 59), (25, 60), (25, 44), (25, 61), (26, 48), (26, 33), (26, 49), (26, 34), (26, 50), (26, 54), (26, 55), (26, 40), (26, 57), (26, 58), (26, 27), (26, 61), (26, 45), (26, 30), (26, 46), (26, 47), (27, 32), (27, 48), (27, 33), (27, 49), (27, 34), (27, 36), (27, 53), (27, 39), (27, 55), (27, 40), (27, 56), (27, 57), (27, 42), (27, 59), (27, 44), (27, 45), (27, 30), (27, 31), (27, 47), (28, 32), (28, 50), (28, 52), (28, 54), (28, 39), (28, 55), (28, 40), (28, 41), (28, 42), (28, 43), (28, 45), (28, 31), (29, 34), (29, 37), (29, 53), (29, 54), (29, 55), (29, 56), (29, 42), (29, 43), (29, 60), (30, 48), (30, 33), (30, 49), (30, 34), (30, 35), (30, 52), (30, 53), (30, 38), (30, 54), (30, 59), (30, 44), (30, 47), (31, 49), (31, 35), (31, 51), (31, 36), (31, 53), (31, 54), (31, 39), (31, 55), (31, 40), (31, 57), (31, 42), (31, 43), (31, 59), (31, 44), (31, 45), (32, 33), (32, 49), (32, 51), (32, 36), (32, 37), (32, 38), (32, 40), (32, 58), (32, 44), (32, 47), (33, 48), (33, 49), (33, 51), (33, 36), (33, 53), (33, 38), (33, 54), (33, 55), (33, 40), (33, 41), (33, 59), (33, 60), (33, 44), (33, 61), (33, 45), (33, 46), (33, 47), (34, 48), (34, 51), (34, 36), (34, 52), (34, 37), (34, 53), (34, 39), (34, 56), (34, 41), (34, 44), (34, 46), (35, 52), (35, 37), (35, 54), (35, 42), (35, 60), (35, 44), (35, 45), (36, 49), (36, 54), (36, 39), (36, 55), (36, 41), (36, 57), (36, 58), (36, 59), (36, 60), (36, 45), (36, 47), (37, 48), (37, 50), (37, 52), (37, 55), (37, 42), (37, 59), (37, 45), (37, 47), (38, 53), (38, 54), (38, 39), (38, 40), (38, 57), (38, 42), (38, 59), (38, 45), (38, 46), (39, 48), (39, 49), (39, 40), (39, 42), (39, 58), (39, 43), (39, 59), (39, 60), (39, 61), (39, 45), (39, 46), (39, 47), (40, 48), (40, 49), (40, 50), (40, 52), (40, 55), (40, 57), (40, 58), (40, 43), (40, 59), (40, 60), (40, 44), (40, 45), (40, 46), (40, 47), (41, 48), (41, 50), (41, 53), (41, 56), (41, 58), (41, 59), (41, 60), (41, 46), (42, 52), (42, 60), (42, 44), (42, 45), (42, 46), (43, 48), (43, 52), (43, 57), (43, 60), (43, 46), (43, 47), (44, 48), (44, 51), (44, 53), (44, 55), (44, 57), (44, 59), (44, 60), (44, 61), (44, 47), (45, 48), (45, 52), (45, 53), (45, 56), (45, 59), (45, 60), (45, 61), (46, 49), (46, 52), (46, 53), (46, 55), (46, 58), (47, 49), (47, 56), (47, 58), (48, 56), (48, 57), (48, 59), (49, 52), (49, 59), (49, 60), (49, 61), (50, 52), (50, 57), (50, 60), (51, 55), (51, 56), (51, 57), (52, 54), (52, 56), (52, 57), (53, 54), (53, 56), (53, 57), (54, 55), (54, 61), (55, 60), (56, 58), (56, 59), (56, 60), (56, 61), (57, 58), (57, 60), (58, 59), (58, 60), (58, 61), (59, 61), (60, 61)],
    ),
    // Corner Case: order = 63
    (
        63, r"~??~`U@aoLr_G\V`YnUdSA[@PG?CjSvrrFONaJODKrXQMOMEcExcwEILVHfUDsB[rGLhVVYJgI?DRSBAgsFwAVzs@gct_AL`NkAoRCaHOaTGWcgPs{@a_s^HLZBaB_[W_o__U|aRGLpdK@{EJ?xQOCcOksK_X@AI`aleB\KDwlOX?_@`_K@SD?QOQ?dAz]?hb{UYvdRRoQPrGKdgfUKIDQM\mZCjJW|?~XcoyIHEr~HycEDToBFD?_DT?bYNaQaQ`BMAYWuyo@Uz{dQwViiepaHfAdaaGO[CHW]ggCka?s@g@b?cbI[a@`BlU^nFxy?YL?R[GKIPm_",
        &[(0, 32), (0, 48), (0, 1), (0, 33), (0, 49), (0, 34), (0, 18), (0, 51), (0, 36), (0, 20), (0, 5), (0, 37), (0, 53), (0, 38), (0, 54), (0, 55), (0, 40), (0, 24), (0, 56), (0, 9), (0, 58), (0, 11), (0, 43), (0, 59), (0, 60), (0, 12), (0, 44), (0, 28), (0, 61), (0, 13), (0, 45), (0, 29), (0, 62), (0, 31), (0, 47), (1, 32), (1, 16), (1, 49), (1, 35), (1, 19), (1, 51), (1, 4), (1, 20), (1, 52), (1, 53), (1, 38), (1, 54), (1, 7), (1, 23), (1, 55), (1, 24), (1, 9), (1, 57), (1, 42), (1, 58), (1, 11), (1, 27), (1, 59), (1, 29), (1, 30), (1, 62), (1, 15), (2, 32), (2, 50), (2, 3), (2, 19), (2, 20), (2, 52), (2, 6), (2, 22), (2, 54), (2, 23), (2, 55), (2, 24), (2, 25), (2, 26), (2, 58), (2, 11), (2, 27), (2, 60), (2, 44), (2, 28), (2, 13), (2, 45), (2, 29), (2, 30), (2, 14), (3, 32), (3, 18), (3, 50), (3, 4), (3, 36), (3, 21), (3, 6), (3, 38), (3, 7), (3, 39), (3, 23), (3, 55), (3, 56), (3, 26), (3, 43), (3, 13), (3, 45), (3, 62), (3, 47), (4, 48), (4, 18), (4, 50), (4, 35), (4, 51), (4, 37), (4, 53), (4, 38), (4, 22), (4, 7), (4, 8), (4, 40), (4, 56), (4, 9), (4, 25), (4, 57), (4, 42), (4, 26), (4, 11), (4, 27), (4, 44), (4, 13), (4, 29), (4, 30), (4, 14), (4, 15), (5, 32), (5, 16), (5, 48), (5, 17), (5, 51), (5, 52), (5, 21), (5, 8), (5, 24), (5, 9), (5, 10), (5, 27), (5, 12), (5, 44), (5, 28), (5, 61), (5, 13), (5, 45), (5, 46), (5, 15), (6, 48), (6, 18), (6, 50), (6, 35), (6, 19), (6, 36), (6, 20), (6, 52), (6, 37), (6, 54), (6, 24), (6, 9), (6, 57), (6, 26), (6, 11), (6, 27), (6, 59), (6, 30), (6, 14), (6, 46), (6, 31), (6, 15), (7, 48), (7, 49), (7, 34), (7, 18), (7, 19), (7, 51), (7, 53), (7, 22), (7, 55), (7, 8), (7, 40), (7, 41), (7, 57), (7, 58), (7, 59), (7, 12), (7, 44), (7, 28), (7, 13), (7, 45), (7, 62), (7, 31), (8, 16), (8, 48), (8, 17), (8, 18), (8, 50), (8, 19), (8, 51), (8, 36), (8, 21), (8, 53), (8, 54), (8, 23), (8, 56), (8, 41), (8, 25), (8, 57), (8, 26), (8, 11), (8, 59), (8, 12), (8, 44), (8, 62), (8, 14), (8, 31), (9, 48), (9, 34), (9, 18), (9, 50), (9, 52), (9, 21), (9, 53), (9, 38), (9, 39), (9, 23), (9, 24), (9, 56), (9, 41), (9, 25), (9, 26), (9, 58), (9, 11), (9, 27), (9, 59), (9, 28), (9, 13), (9, 31), (10, 33), (10, 17), (10, 49), (10, 34), (10, 18), (10, 19), (10, 20), (10, 53), (10, 38), (10, 39), (10, 55), (10, 40), (10, 41), (10, 11), (10, 43), (10, 27), (10, 12), (10, 28), (10, 61), (10, 13), (10, 29), (10, 62), (10, 31), (11, 35), (11, 38), (11, 22), (11, 23), (11, 40), (11, 56), (11, 41), (11, 25), (11, 43), (11, 59), (11, 60), (11, 44), (11, 28), (11, 61), (11, 31), (11, 47), (12, 17), (12, 51), (12, 20), (12, 52), (12, 37), (12, 21), (12, 53), (12, 22), (12, 24), (12, 56), (12, 42), (12, 58), (12, 60), (12, 44), (12, 61), (12, 13), (12, 29), (13, 32), (13, 48), (13, 17), (13, 49), (13, 18), (13, 50), (13, 36), (13, 20), (13, 52), (13, 37), (13, 21), (13, 22), (13, 55), (13, 24), (13, 25), (13, 57), (13, 27), (13, 59), (13, 28), (13, 45), (13, 30), (14, 32), (14, 33), (14, 18), (14, 50), (14, 53), (14, 23), (14, 40), (14, 24), (14, 56), (14, 26), (14, 58), (14, 43), (14, 27), (14, 61), (14, 45), (14, 30), (14, 46), (14, 15), (14, 47), (15, 48), (15, 33), (15, 17), (15, 18), (15, 35), (15, 51), (15, 20), (15, 37), (15, 38), (15, 54), (15, 39), (15, 55), (15, 56), (15, 25), (15, 57), (15, 42), (15, 58), (15, 28), (15, 61), (16, 32), (16, 48), (16, 34), (16, 18), (16, 21), (16, 22), (16, 56), (16, 25), (16, 57), (16, 26), (16, 60), (16, 28), (16, 46), (16, 47), (17, 33), (17, 49), (17, 19), (17, 51), (17, 36), (17, 21), (17, 53), (17, 41), (17, 25), (17, 57), (17, 26), (17, 27), (17, 59), (17, 60), (17, 28), (17, 61), (17, 45), (18, 33), (18, 49), (18, 35), (18, 19), (18, 36), (18, 52), (18, 56), (18, 41), (18, 57), (18, 42), (18, 26), (18, 44), (18, 62), (18, 46), (19, 48), (19, 49), (19, 34), (19, 50), (19, 51), (19, 36), (19, 52), (19, 37), (19, 21), (19, 55), (19, 58), (19, 59), (19, 44), (19, 28), (19, 61), (19, 30), (19, 31), (20, 32), (20, 48), (20, 34), (20, 35), (20, 51), (20, 52), (20, 37), (20, 21), (20, 23), (20, 40), (20, 56), (20, 25), (20, 57), (20, 26), (20, 43), (20, 28), (21, 50), (21, 36), (21, 37), (21, 38), (21, 39), (21, 23), (21, 40), (21, 24), (21, 56), (21, 58), (21, 44), (21, 61), (21, 30), (21, 62), (21, 47), (22, 48), (22, 49), (22, 35), (22, 52), (22, 37), (22, 38), (22, 55), (22, 24), (22, 41), (22, 57), (22, 42), (22, 44), (22, 28), (22, 61), (22, 62), (22, 31), (23, 32), (23, 33), (23, 49), (23, 51), (23, 37), (23, 53), (23, 38), (23, 40), (23, 25), (23, 27), (23, 44), (23, 29), (23, 30), (23, 47), (24, 48), (24, 34), (24, 36), (24, 53), (24, 54), (24, 40), (24, 41), (24, 25), (24, 57), (24, 27), (24, 60), (24, 45), (24, 62), (24, 46), (24, 31), (24, 47), (25, 48), (25, 35), (25, 51), (25, 36), (25, 55), (25, 40), (25, 41), (25, 58), (25, 43), (25, 44), (25, 61), (25, 29), (25, 62), (25, 31), (25, 47), (26, 32), (26, 33), (26, 49), (26, 50), (26, 51), (26, 36), (26, 52), (26, 37), (26, 54), (26, 57), (26, 27), (26, 59), (26, 28), (26, 61), (26, 62), (26, 46), (26, 31), (27, 32), (27, 48), (27, 33), (27, 34), (27, 36), (27, 55), (27, 42), (27, 60), (27, 61), (27, 29), (27, 30), (27, 31), (27, 47), (28, 48), (28, 33), (28, 50), (28, 51), (28, 52), (28, 54), (28, 39), (28, 57), (28, 44), (28, 61), (28, 30), (28, 31), (28, 47), (29, 32), (29, 48), (29, 33), (29, 51), (29, 37), (29, 53), (29, 40), (29, 42), (29, 58), (29, 43), (29, 59), (29, 44), (29, 61), (29, 31), (30, 48), (30, 33), (30, 50), (30, 35), (30, 38), (30, 54), (30, 39), (30, 40), (30, 57), (30, 42), (30, 60), (30, 61), (30, 47), (31, 32), (31, 34), (31, 35), (31, 53), (31, 38), (31, 39), (31, 56), (31, 43), (31, 59), (31, 62), (31, 47), (32, 33), (32, 49), (32, 52), (32, 37), (32, 38), (32, 54), (32, 55), (32, 41), (32, 59), (32, 61), (32, 47), (33, 48), (33, 49), (33, 50), (33, 51), (33, 37), (33, 53), (33, 39), (33, 40), (33, 56), (33, 41), (33, 57), (33, 42), (33, 43), (33, 61), (33, 47), (34, 51), (34, 39), (34, 41), (34, 57), (34, 42), (34, 58), (34, 60), (34, 61), (34, 46), (35, 48), (35, 51), (35, 36), (35, 52), (35, 37), (35, 53), (35, 39), (35, 40), (35, 56), (35, 59), (35, 60), (35, 44), (35, 61), (35, 45), (36, 49), (36, 51), (36, 38), (36, 39), (36, 56), (36, 57), (36, 42), (36, 45), (37, 48), (37, 50), (37, 53), (37, 38), (37, 55), (37, 41), (37, 57), (37, 44), (37, 62), (37, 46), (38, 50), (38, 51), (38, 53), (38, 39), (38, 55), (38, 40), (38, 56), (38, 43), (38, 60), (38, 44), (38, 62), (39, 49), (39, 50), (39, 52), (39, 53), (39, 54), (39, 40), (39, 56), (39, 41), (39, 43), (39, 59), (39, 44), (39, 61), (40, 48), (40, 52), (40, 56), (40, 58), (40, 60), (40, 44), (40, 61), (40, 46), (41, 48), (41, 49), (41, 55), (41, 57), (41, 42), (41, 58), (41, 61), (41, 45), (41, 47), (42, 49), (42, 50), (42, 52), (42, 55), (42, 56), (42, 57), (42, 58), (42, 61), (42, 45), (43, 48), (43, 50), (43, 52), (43, 54), (43, 55), (43, 56), (43, 60), (43, 61), (43, 62), (43, 47), (44, 49), (44, 50), (44, 54), (44, 56), (44, 60), (44, 61), (45, 51), (45, 56), (45, 60), (45, 62), (46, 48), (46, 50), (46, 51), (46, 52), (46, 54), (46, 56), (46, 57), (46, 47), (47, 48), (47, 50), (47, 51), (47, 52), (47, 54), (47, 56), (47, 59), (47, 61), (48, 49), (48, 51), (48, 52), (48, 53), (48, 58), (48, 59), (48, 60), (48, 61), (48, 62), (49, 50), (49, 51), (49, 52), (49, 53), (49, 54), (49, 55), (49, 61), (50, 51), (50, 52), (50, 56), (50, 57), (50, 59), (50, 61), (51, 52), (52, 55), (52, 60), (52, 61), (52, 62), (53, 54), (53, 55), (53, 56), (53, 57), (53, 58), (53, 62), (54, 57), (55, 56), (55, 62), (56, 58), (56, 62), (57, 62), (58, 59), (59, 60), (59, 62)],
    ),
];