/* 

  Map coloring in Picat.

  Ported from the B-Prolog model
  http://www.probp.com/cp_sat_lp/color.pl
  """
  by Neng-Fa Zhou, Jan. 2012
  """

  Variant of http://www.hakank.org/picat/color.pi

  This variant use neqs/1 instead of plain #!=/2 .

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


import cp. % only supported in the cp module


main => go.

go => 
  time2(color(125,5)).

go2 => 
  time2(color1(125,5)).


%
% using neqs/1: 0.17s
%
color(NV, NC) =>
    println([nv=NV, nc=NC]),
    A = new_list(NV),
    A :: 1..NC,

    % Z :: 1..NC,
    Edges = findall([From,To], (edge(From,To), From < To)),

    %% This don't work: it don't yield the constraints, just plain variables.
    % Neqs = findall( A[From] #!= A[To], (edge(From,To), From < To)),

    %% Alt 1.
    %% This works and is quite fast: 0.172s / 0 backtracks (without optimization 0.04s)
    %% Solution: 
    %% [2,2,2,2,3,4,1,5,4,3,3,1,2,3,1,5,5,4,4,5,2,3,2,1,3,3,4,3,2,5,3,3,4,5,2,2,1,2,4,3,5,4,3,5,3,1,5,5,1,3,5,5,2,4,4,2,2,2,3,4,3,1,1,3,4,3,4,2,2,4,1,5,2,4,1,1,1,5,3,4,3,1,5,2,4,5,1,2,4,4,1,1,5,4,5,3,5,3,2,1,4,3,3,5,4,3,2,1,5,5,4,4,1,1,1,2,2,3,1,3,1,4,2,2,5]
    Neqs = [],
    foreach([I,J] in Edges)
       Neqs := Neqs ++ [A[I] #!= A[J]]
       % Neqs := [A[I] #!= A[J]|Neqs] % this is much slower (it's another order of constraints)
    end,


    %% Alt 2.
    %% Using this is much slower: 5.42s / 0 backtracks (same time w/o optimization)
    %% Solution:
    %% [3,5,1,5,5,4,3,1,2,3,3,5,3,3,3,1,2,2,3,2,3,3,5,3,5,5,2,5,3,4,5,4,2,4,3,2,3,4,4,5,4,2,5,4,5,1,4,4,4,3,4,2,1,5,2,3,5,2,2,1,2,2,3,2,2,2,2,1,1,4,4,4,2,3,1,1,1,4,3,2,5,3,2,3,3,4,1,4,2,1,3,1,4,5,1,5,1,5,5,3,2,5,5,2,1,5,2,1,2,3,1,1,1,1,3,2,5,5,1,5,1,1,4,4,4]
    %% Also, it don't generate the same solution and alt 1, even though Neqs should
    %% be the same and the labeling is the same.
    % NumEdges = length(Edges),
    % Neqs = new_list(NumEdges),
    % foreach({[I,J],C} in zip(Edges,1..NumEdges))
    %    Neqs[C] := A[I] #!= A[J]
    % end,

    %% Alt 3
    %% 5.3s / 0 backtracks (same w/o optimization)
    %% Solution: same as alt 2.
    %% [3,5,1,5,5,4,3,1,2,3,3,5,3,3,3,1,2,2,3,2,3,3,5,3,5,5,2,5,3,4,5,4,2,4,3,2,3,4,4,5,4,2,5,4,5,1,4,4,4,3,4,2,1,5,2,3,5,2,2,1,2,2,3,2,2,2,2,1,1,4,4,4,2,3,1,1,1,4,3,2,5,3,2,3,3,4,1,4,2,1,3,1,4,5,1,5,1,5,5,3,2,5,5,2,1,5,2,1,2,3,1,1,1,1,3,2,5,5,1,5,1,1,4,4,4]
    % gen(Edges,A,[],Neqs),

    %% Alt 4: 
    %% 5.3s / 0 backtracks
    %% [3,5,1,5,5,4,3,1,2,3,3,5,3,3,3,1,2,2,3,2,3,3,5,3,5,5,2,5,3,4,5,4,2,4,3,2,3,4,4,5,4,2,5,4,5,1,4,4,4,3,4,2,1,5,2,3,5,2,2,1,2,2,3,2,2,2,2,1,1,4,4,4,2,3,1,1,1,4,3,2,5,3,2,3,3,4,1,4,2,1,3,1,4,5,1,5,1,5,5,3,2,5,5,2,1,5,2,1,2,3,1,1,1,1,3,2,5,5,1,5,1,1,4,4,4]
    % Neqs = [A[I] #!= A[J] : [I,J] in Edges],

    % println(neqs=Neqs),

    % Printing _only_ the lengths (Neqs.length) makes it much slower (5.3s vs 0.17s).
    % However, using length(Neqs) is much faster.
    % println(neqs=Neqs.length),
    % println(neqs=length(Neqs)), % much faster than List.length


    % Z #= max(A), % placing the Z constraint here makes it much slower (15.5s vs 0.17s)!

    % What is the impact of sorting Neqs before? For variant 2..4 it's none, variant 1 takes much longer (33s!).
    % Neqs1 = sort(Neqs),
    Neqs1 = Neqs,
    neqs(Neqs1),

    %% Solution for variant 1
    % Test = [2,2,2,2,3,4,1,5,4,3,3,1,2,3,1,5,5,4,4,5,2,3,2,1,3,3,4,3,2,5,3,3,4,5,2,2,1,2,4,3,5,4,3,5,3,1,5,5,1,3,5,5,2,4,4,2,2,2,3,4,3,1,1,3,4,3,4,2,2,4,1,5,2,4,1,1,1,5,3,4,3,1,5,2,4,5,1,2,4,4,1,1,5,4,5,3,5,3,2,1,4,3,3,5,4,3,2,1,5,5,4,4,1,1,1,2,2,3,1,3,1,4,2,2,5],

    %% Solution for variant 2..4
    % Test = [3,5,1,5,5,4,3,1,2,3,3,5,3,3,3,1,2,2,3,2,3,3,5,3,5,5,2,5,3,4,5,4,2,4,3,2,3,4,4,5,4,2,5,4,5,1,4,4,4,3,4,2,1,5,2,3,5,2,2,1,2,2,3,2,2,2,2,1,1,4,4,4,2,3,1,1,1,4,3,2,5,3,2,3,3,4,1,4,2,1,3,1,4,5,1,5,1,5,5,3,2,5,5,2,1,5,2,1,2,3,1,1,1,1,3,2,5,5,1,5,1,1,4,4,4],

    % foreach(I in 1..length(A))
    %    A[I] #= Test[I]
    % end,

    Z #= max(A),  % faster if placed here (0.17s)

    % println(a=A),
    println(solve),
    Vars = A ++ Neqs1,
    % time2(solve($[ffc,split,min(Z)], Neqs1 ++ A)), % alt 1: 0.17s
    % time2(solve($[ffc,split,min(Z)], Vars)), % alt 1: 0.17s
    % time2(solve($[ffc,split], Neqs ++ A)), % alt 1: 0.04s

    time2(solve($[ff,min(Z)], Vars)), % alt 1: 

    println(A),
    println(z=Z),
    nl.

%
% without neqs (no optimization): 0.67s (0 backtracks) 
% without neqs (with optimization): 1.17s (0 backtracks) 
%
color1(NV,NC) =>
    A = new_list(NV),
    A :: 1..NC,
    Edges = findall([From,To], (edge(From,To), From < To)),
    foreach([From,To] in Edges)
        A[From] #!= A[To]
    end,

    Z #= max(A),

    println(solve),
    solve($[ffc,split,min(Z)], A),
    println(A),
    nl.


% generate #!= constraints given the Edges
gen([],_A,C0,C) ?=> C = C0.reverse().
gen([[From,To]|Edges],A,C0, C) =>
  gen(Edges,A,[A[From] #!= A[To]|C0], C).


index(-,-)	
edge(1,17).
edge(1,25).
edge(1,27).
edge(1,39).
edge(1,45).
edge(1,62).
edge(1,70).
edge(1,77).
edge(1,93).
edge(1,95).
edge(1,96).
edge(1,103).
edge(1,108).
edge(1,125).
edge(2,6).
edge(2,16).
edge(2,18).
edge(2,30).
edge(2,49).
edge(2,51).
edge(2,52).
edge(2,78).
edge(2,82).
edge(2,109).
edge(3,5).
edge(3,6).
edge(3,15).
edge(3,20).
edge(3,24).
edge(3,28).
edge(3,40).
edge(3,42).
edge(42,3).
edge(3,71).
edge(71,3).
edge(3,79).
edge(79,3).
edge(3,80).
edge(80,3).
edge(3,86).
edge(86,3).
edge(3,94).
edge(94,3).
edge(3,101).
edge(101,3).
edge(3,102).
edge(102,3).
edge(3,125).
edge(125,3).
edge(4,15).
edge(15,4).
edge(4,37).
edge(37,4).
edge(4,52).
edge(52,4).
edge(4,63).
edge(63,4).
edge(4,66).
edge(66,4).
edge(4,70).
edge(70,4).
edge(4,97).
edge(97,4).
edge(4,112).
edge(112,4).
edge(4,122).
edge(122,4).
edge(5,18).
edge(18,5).
edge(5,20).
edge(20,5).
edge(5,27).
edge(27,5).
edge(5,29).
edge(29,5).
edge(5,37).
edge(37,5).
edge(5,39).
edge(39,5).
edge(5,56).
edge(56,5).
edge(5,73).
edge(73,5).
edge(5,74).
edge(74,5).
edge(5,76).
edge(76,5).
edge(5,87).
edge(87,5).
edge(5,88).
edge(88,5).
edge(5,105).
edge(105,5).
edge(5,115).
edge(115,5).
edge(5,124).
edge(124,5).
edge(6,15).
edge(15,6).
edge(6,35).
edge(35,6).
edge(6,59).
edge(59,6).
edge(6,61).
edge(61,6).
edge(6,68).
edge(68,6).
edge(6,77).
edge(77,6).
edge(6,81).
edge(81,6).
edge(6,99).
edge(99,6).
edge(6,102).
edge(102,6).
edge(6,104).
edge(104,6).
edge(6,113).
edge(113,6).
edge(6,120).
edge(120,6).
edge(7,36).
edge(36,7).
edge(7,58).
edge(58,7).
edge(7,60).
edge(60,7).
edge(7,61).
edge(61,7).
edge(7,66).
edge(66,7).
edge(7,70).
edge(70,7).
edge(7,90).
edge(90,7).
edge(7,95).
edge(95,7).
edge(7,104).
edge(104,7).
edge(7,125).
edge(125,7).
edge(8,23).
edge(23,8).
edge(8,24).
edge(24,8).
edge(8,26).
edge(26,8).
edge(8,65).
edge(65,8).
edge(8,70).
edge(70,8).
edge(8,102).
edge(102,8).
edge(8,103).
edge(103,8).
edge(8,115).
edge(115,8).
edge(8,116).
edge(116,8).
edge(8,117).
edge(117,8).
edge(9,21).
edge(21,9).
edge(9,41).
edge(41,9).
edge(9,43).
edge(43,9).
edge(9,56).
edge(56,9).
edge(9,93).
edge(93,9).
edge(9,113).
edge(113,9).
edge(10,12).
edge(12,10).
edge(10,49).
edge(49,10).
edge(10,55).
edge(55,10).
edge(10,58).
edge(58,10).
edge(10,68).
edge(68,10).
edge(10,72).
edge(72,10).
edge(10,76).
edge(76,10).
edge(10,99).
edge(99,10).
edge(10,111).
edge(111,10).
edge(10,119).
edge(119,10).
edge(11,20).
edge(20,11).
edge(11,27).
edge(27,11).
edge(11,30).
edge(30,11).
edge(11,38).
edge(38,11).
edge(11,57).
edge(57,11).
edge(11,67).
edge(67,11).
edge(11,68).
edge(68,11).
edge(11,71).
edge(71,11).
edge(11,75).
edge(75,11).
edge(11,77).
edge(77,11).
edge(11,86).
edge(86,11).
edge(11,112).
edge(112,11).
edge(11,123).
edge(123,11).
edge(11,124).
edge(124,11).
edge(12,20).
edge(20,12).
edge(12,47).
edge(47,12).
edge(12,55).
edge(55,12).
edge(12,64).
edge(64,12).
edge(12,69).
edge(69,12).
edge(12,70).
edge(70,12).
edge(12,86).
edge(86,12).
edge(12,90).
edge(90,12).
edge(12,101).
edge(101,12).
edge(12,112).
edge(112,12).
edge(13,27).
edge(27,13).
edge(13,28).
edge(28,13).
edge(13,31).
edge(31,13).
edge(13,41).
edge(41,13).
edge(13,44).
edge(44,13).
edge(13,48).
edge(48,13).
edge(13,54).
edge(54,13).
edge(13,62).
edge(62,13).
edge(13,65).
edge(65,13).
edge(13,67).
edge(67,13).
edge(13,70).
edge(70,13).
edge(13,87).
edge(87,13).
edge(13,118).
edge(118,13).
edge(13,122).
edge(122,13).
edge(14,46).
edge(46,14).
edge(14,48).
edge(48,14).
edge(14,54).
edge(54,14).
edge(14,62).
edge(62,14).
edge(14,72).
edge(72,14).
edge(14,75).
edge(75,14).
edge(14,76).
edge(76,14).
edge(14,87).
edge(87,14).
edge(14,89).
edge(89,14).
edge(14,104).
edge(104,14).
edge(14,105).
edge(105,14).
edge(14,114).
edge(114,14).
edge(14,123).
edge(123,14).
edge(15,40).
edge(40,15).
edge(15,53).
edge(53,15).
edge(15,68).
edge(68,15).
edge(15,81).
edge(81,15).
edge(15,83).
edge(83,15).
edge(15,90).
edge(90,15).
edge(15,96).
edge(96,15).
edge(15,99).
edge(99,15).
edge(15,106).
edge(106,15).
edge(15,118).
edge(118,15).
edge(16,31).
edge(31,16).
edge(16,35).
edge(35,16).
edge(16,37).
edge(37,16).
edge(16,49).
edge(49,16).
edge(16,66).
edge(66,16).
edge(16,67).
edge(67,16).
edge(16,71).
edge(71,16).
edge(16,80).
edge(80,16).
edge(16,89).
edge(89,16).
edge(16,102).
edge(102,16).
edge(16,120).
edge(120,16).
edge(17,28).
edge(28,17).
edge(17,29).
edge(29,17).
edge(17,45).
edge(45,17).
edge(17,49).
edge(49,17).
edge(17,81).
edge(81,17).
edge(17,84).
edge(84,17).
edge(17,96).
edge(96,17).
edge(17,98).
edge(98,17).
edge(17,111).
edge(111,17).
edge(17,112).
edge(112,17).
edge(18,34).
edge(34,18).
edge(18,35).
edge(35,18).
edge(18,49).
edge(49,18).
edge(18,71).
edge(71,18).
edge(18,78).
edge(78,18).
edge(18,81).
edge(81,18).
edge(18,86).
edge(86,18).
edge(18,98).
edge(98,18).
edge(18,99).
edge(99,18).
edge(18,119).
edge(119,18).
edge(18,123).
edge(123,18).
edge(19,36).
edge(36,19).
edge(19,46).
edge(46,19).
edge(19,48).
edge(48,19).
edge(19,61).
edge(61,19).
edge(19,64).
edge(64,19).
edge(19,77).
edge(77,19).
edge(19,78).
edge(78,19).
edge(19,97).
edge(97,19).
edge(19,102).
edge(102,19).
edge(19,103).
edge(103,19).
edge(19,107).
edge(107,19).
edge(19,108).
edge(108,19).
edge(19,118).
edge(118,19).
edge(20,60).
edge(60,20).
edge(20,70).
edge(70,20).
edge(20,71).
edge(71,20).
edge(20,74).
edge(74,20).
edge(20,76).
edge(76,20).
edge(20,94).
edge(94,20).
edge(20,114).
edge(114,20).
edge(20,124).
edge(124,20).
edge(21,25).
edge(25,21).
edge(21,26).
edge(26,21).
edge(21,31).
edge(31,21).
edge(21,33).
edge(33,21).
edge(21,34).
edge(34,21).
edge(21,47).
edge(47,21).
edge(21,80).
edge(80,21).
edge(21,90).
edge(90,21).
edge(21,103).
edge(103,21).
edge(21,119).
edge(119,21).
edge(22,33).
edge(33,22).
edge(22,51).
edge(51,22).
edge(22,58).
edge(58,22).
edge(22,60).
edge(60,22).
edge(22,83).
edge(83,22).
edge(22,90).
edge(90,22).
edge(22,99).
edge(99,22).
edge(22,108).
edge(108,22).
edge(22,119).
edge(119,22).
edge(22,121).
edge(121,22).
edge(22,122).
edge(122,22).
edge(23,27).
edge(27,23).
edge(23,34).
edge(34,23).
edge(23,42).
edge(42,23).
edge(23,46).
edge(46,23).
edge(23,50).
edge(50,23).
edge(23,59).
edge(59,23).
edge(23,74).
edge(74,23).
edge(23,90).
edge(90,23).
edge(23,110).
edge(110,23).
edge(23,121).
edge(121,23).
edge(24,28).
edge(28,24).
edge(24,31).
edge(31,24).
edge(24,43).
edge(43,24).
edge(24,44).
edge(44,24).
edge(24,48).
edge(48,24).
edge(24,52).
edge(52,24).
edge(24,55).
edge(55,24).
edge(24,57).
edge(57,24).
edge(24,97).
edge(97,24).
edge(24,99).
edge(99,24).
edge(24,101).
edge(101,24).
edge(24,102).
edge(102,24).
edge(24,109).
edge(109,24).
edge(24,112).
edge(112,24).
edge(24,125).
edge(125,24).
edge(25,36).
edge(36,25).
edge(25,37).
edge(37,25).
edge(25,41).
edge(41,25).
edge(25,52).
edge(52,25).
edge(25,67).
edge(67,25).
edge(25,70).
edge(70,25).
edge(25,77).
edge(77,25).
edge(25,83).
edge(83,25).
edge(25,91).
edge(91,25).
edge(25,92).
edge(92,25).
edge(25,93).
edge(93,25).
edge(25,100).
edge(100,25).
edge(25,114).
edge(114,25).
edge(25,125).
edge(125,25).
edge(26,48).
edge(48,26).
edge(26,51).
edge(51,26).
edge(26,75).
edge(75,26).
edge(26,92).
edge(92,26).
edge(26,95).
edge(95,26).
edge(26,109).
edge(109,26).
edge(26,112).
edge(112,26).
edge(26,113).
edge(113,26).
edge(26,114).
edge(114,26).
edge(27,28).
edge(28,27).
edge(27,30).
edge(30,27).
edge(27,53).
edge(53,27).
edge(27,81).
edge(81,27).
edge(27,82).
edge(82,27).
edge(27,88).
edge(88,27).
edge(27,92).
edge(92,27).
edge(27,103).
edge(103,27).
edge(27,108).
edge(108,27).
edge(27,113).
edge(113,27).
edge(27,123).
edge(123,27).
edge(28,33).
edge(33,28).
edge(28,34).
edge(34,28).
edge(28,52).
edge(52,28).
edge(28,62).
edge(62,28).
edge(28,63).
edge(63,28).
edge(28,74).
edge(74,28).
edge(28,77).
edge(77,28).
edge(28,89).
edge(89,28).
edge(28,93).
edge(93,28).
edge(28,95).
edge(95,28).
edge(29,30).
edge(30,29).
edge(29,39).
edge(39,29).
edge(29,43).
edge(43,29).
edge(29,51).
edge(51,29).
edge(29,92).
edge(92,29).
edge(29,97).
edge(97,29).
edge(29,108).
edge(108,29).
edge(30,36).
edge(36,30).
edge(30,45).
edge(45,30).
edge(30,53).
edge(53,30).
edge(30,54).
edge(54,30).
edge(30,67).
edge(67,30).
edge(30,92).
edge(92,30).
edge(30,105).
edge(105,30).
edge(30,106).
edge(106,30).
edge(30,114).
edge(114,30).
edge(30,118).
edge(118,30).
edge(31,36).
edge(36,31).
edge(31,44).
edge(44,31).
edge(31,51).
edge(51,31).
edge(31,55).
edge(55,31).
edge(31,65).
edge(65,31).
edge(31,69).
edge(69,31).
edge(31,70).
edge(70,31).
edge(31,86).
edge(86,31).
edge(31,87).
edge(87,31).
edge(31,121).
edge(121,31).
edge(32,33).
edge(33,32).
edge(32,84).
edge(84,32).
edge(32,85).
edge(85,32).
edge(32,113).
edge(113,32).
edge(33,35).
edge(35,33).
edge(33,46).
edge(46,33).
edge(33,72).
edge(72,33).
edge(33,82).
edge(82,33).
edge(33,86).
edge(86,33).
edge(33,88).
edge(88,33).
edge(33,91).
edge(91,33).
edge(33,96).
edge(96,33).
edge(33,97).
edge(97,33).
edge(34,40).
edge(40,34).
edge(34,50).
edge(50,34).
edge(34,55).
edge(55,34).
edge(34,57).
edge(57,34).
edge(34,62).
edge(62,34).
edge(34,76).
edge(76,34).
edge(34,91).
edge(91,34).
edge(34,112).
edge(112,34).
edge(35,43).
edge(43,35).
edge(35,71).
edge(71,35).
edge(35,81).
edge(81,35).
edge(35,94).
edge(94,35).
edge(35,95).
edge(95,35).
edge(35,103).
edge(103,35).
edge(35,109).
edge(109,35).
edge(35,120).
edge(120,35).
edge(36,87).
edge(87,36).
edge(36,102).
edge(102,36).
edge(36,118).
edge(118,36).
edge(36,120).
edge(120,36).
edge(36,122).
edge(122,36).
edge(37,44).
edge(44,37).
edge(37,83).
edge(83,37).
edge(37,88).
edge(88,37).
edge(37,90).
edge(90,37).
edge(37,93).
edge(93,37).
edge(37,96).
edge(96,37).
edge(37,111).
edge(111,37).
edge(37,122).
edge(122,37).
edge(37,123).
edge(123,37).
edge(37,125).
edge(125,37).
edge(38,43).
edge(43,38).
edge(38,50).
edge(50,38).
edge(38,52).
edge(52,38).
edge(38,59).
edge(59,38).
edge(38,64).
edge(64,38).
edge(38,87).
edge(87,38).
edge(38,90).
edge(90,38).
edge(38,101).
edge(101,38).
edge(38,113).
edge(113,38).
edge(39,46).
edge(46,39).
edge(39,61).
edge(61,39).
edge(39,64).
edge(64,39).
edge(39,82).
edge(82,39).
edge(39,103).
edge(103,39).
edge(39,113).
edge(113,39).
edge(39,119).
edge(119,39).
edge(40,46).
edge(46,40).
edge(40,49).
edge(49,40).
edge(40,51).
edge(51,40).
edge(40,55).
edge(55,40).
edge(40,109).
edge(109,40).
edge(40,116).
edge(116,40).
edge(41,42).
edge(42,41).
edge(41,61).
edge(61,41).
edge(41,75).
edge(75,41).
edge(41,89).
edge(89,41).
edge(41,105).
edge(105,41).
edge(41,108).
edge(108,41).
edge(41,113).
edge(113,41).
edge(41,115).
edge(115,41).
edge(41,121).
edge(121,41).
edge(42,47).
edge(47,42).
edge(42,76).
edge(76,42).
edge(42,103).
edge(103,42).
edge(42,110).
edge(110,42).
edge(42,113).
edge(113,42).
edge(42,119).
edge(119,42).
edge(42,123).
edge(123,42).
edge(43,49).
edge(49,43).
edge(43,65).
edge(65,43).
edge(43,67).
edge(67,43).
edge(43,68).
edge(68,43).
edge(43,74).
edge(74,43).
edge(43,80).
edge(80,43).
edge(43,112).
edge(112,43).
edge(44,90).
edge(90,44).
edge(44,94).
edge(94,44).
edge(44,106).
edge(106,44).
edge(44,107).
edge(107,44).
edge(44,114).
edge(114,44).
edge(44,117).
edge(117,44).
edge(45,56).
edge(56,45).
edge(45,60).
edge(60,45).
edge(45,71).
edge(71,45).
edge(45,77).
edge(77,45).
edge(45,87).
edge(87,45).
edge(45,101).
edge(101,45).
edge(46,67).
edge(67,46).
edge(46,79).
edge(79,46).
edge(47,57).
edge(57,47).
edge(47,63).
edge(63,47).
edge(47,107).
edge(107,47).
edge(47,111).
edge(111,47).
edge(47,120).
edge(120,47).
edge(48,53).
edge(53,48).
edge(48,61).
edge(61,48).
edge(48,65).
edge(65,48).
edge(48,68).
edge(68,48).
edge(48,80).
edge(80,48).
edge(48,84).
edge(84,48).
edge(48,98).
edge(98,48).
edge(48,99).
edge(99,48).
edge(48,114).
edge(114,48).
edge(49,53).
edge(53,49).
edge(49,94).
edge(94,49).
edge(50,51).
edge(51,50).
edge(50,52).
edge(52,50).
edge(50,58).
edge(58,50).
edge(50,72).
edge(72,50).
edge(50,92).
edge(92,50).
edge(50,95).
edge(95,50).
edge(50,108).
edge(108,50).
edge(50,109).
edge(109,50).
edge(50,113).
edge(113,50).
edge(50,117).
edge(117,50).
edge(50,119).
edge(119,50).
edge(50,123).
edge(123,50).
edge(51,56).
edge(56,51).
edge(51,101).
edge(101,51).
edge(51,105).
edge(105,51).
edge(51,106).
edge(106,51).
edge(51,115).
edge(115,51).
edge(51,116).
edge(116,51).
edge(51,118).
edge(118,51).
edge(52,63).
edge(63,52).
edge(52,91).
edge(91,52).
edge(52,103).
edge(103,52).
edge(52,108).
edge(108,52).
edge(52,111).
edge(111,52).
edge(52,112).
edge(112,52).
edge(53,70).
edge(70,53).
edge(53,80).
edge(80,53).
edge(53,98).
edge(98,53).
edge(53,118).
edge(118,53).
edge(53,120).
edge(120,53).
edge(54,88).
edge(88,54).
edge(54,92).
edge(92,54).
edge(54,104).
edge(104,54).
edge(54,114).
edge(114,54).
edge(54,115).
edge(115,54).
edge(55,75).
edge(75,55).
edge(55,82).
edge(82,55).
edge(55,96).
edge(96,55).
edge(55,99).
edge(99,55).
edge(55,103).
edge(103,55).
edge(55,115).
edge(115,55).
edge(55,125).
edge(125,55).
edge(56,59).
edge(59,56).
edge(56,64).
edge(64,56).
edge(56,66).
edge(66,56).
edge(56,75).
edge(75,56).
edge(56,76).
edge(76,56).
edge(56,77).
edge(77,56).
edge(56,104).
edge(104,56).
edge(56,105).
edge(105,56).
edge(56,106).
edge(106,56).
edge(56,109).
edge(109,56).
edge(56,112).
edge(112,56).
edge(56,119).
edge(119,56).
edge(57,63).
edge(63,57).
edge(57,65).
edge(65,57).
edge(57,66).
edge(66,57).
edge(57,75).
edge(75,57).
edge(57,80).
edge(80,57).
edge(57,87).
edge(87,57).
edge(57,89).
edge(89,57).
edge(57,95).
edge(95,57).
edge(57,100).
edge(100,57).
edge(58,76).
edge(76,58).
edge(58,77).
edge(77,58).
edge(58,79).
edge(79,58).
edge(58,81).
edge(81,58).
edge(58,91).
edge(91,58).
edge(58,94).
edge(94,58).
edge(58,97).
edge(97,58).
edge(58,108).
edge(108,58).
edge(58,113).
edge(113,58).
edge(59,70).
edge(70,59).
edge(59,74).
edge(74,59).
edge(59,95).
edge(95,59).
edge(59,113).
edge(113,59).
edge(59,124).
edge(124,59).
edge(60,64).
edge(64,60).
edge(60,96).
edge(96,60).
edge(60,98).
edge(98,60).
edge(60,115).
edge(115,60).
edge(60,124).
edge(124,60).
edge(61,63).
edge(63,61).
edge(61,71).
edge(71,61).
edge(61,92).
edge(92,61).
edge(61,94).
edge(94,61).
edge(61,100).
edge(100,61).
edge(61,108).
edge(108,61).
edge(61,115).
edge(115,61).
edge(61,124).
edge(124,61).
edge(62,68).
edge(68,62).
edge(62,69).
edge(69,62).
edge(62,93).
edge(93,62).
edge(62,94).
edge(94,62).
edge(62,105).
edge(105,62).
edge(62,110).
edge(110,62).
edge(62,112).
edge(112,62).
edge(62,120).
edge(120,62).
edge(62,124).
edge(124,62).
edge(62,125).
edge(125,62).
edge(63,65).
edge(65,63).
edge(63,68).
edge(68,63).
edge(63,73).
edge(73,63).
edge(63,86).
edge(86,63).
edge(63,89).
edge(89,63).
edge(63,90).
edge(90,63).
edge(63,96).
edge(96,63).
edge(63,105).
edge(105,63).
edge(63,106).
edge(106,63).
edge(63,112).
edge(112,63).
edge(64,68).
edge(68,64).
edge(64,72).
edge(72,64).
edge(64,77).
edge(77,64).
edge(64,85).
edge(85,64).
edge(64,95).
edge(95,64).
edge(64,110).
edge(110,64).
edge(64,113).
edge(113,64).
edge(64,115).
edge(115,64).
edge(64,117).
edge(117,64).
edge(65,78).
edge(78,65).
edge(65,97).
edge(97,65).
edge(65,102).
edge(102,65).
edge(66,68).
edge(68,66).
edge(66,70).
edge(70,66).
edge(66,71).
edge(71,66).
edge(66,76).
edge(76,66).
edge(66,82).
edge(82,66).
edge(66,88).
edge(88,66).
edge(66,91).
edge(91,66).
edge(66,122).
edge(122,66).
edge(67,68).
edge(68,67).
edge(67,69).
edge(69,67).
edge(67,91).
edge(91,67).
edge(67,125).
edge(125,67).
edge(68,71).
edge(71,68).
edge(68,83).
edge(83,68).
edge(68,102).
edge(102,68).
edge(68,104).
edge(104,68).
edge(69,74).
edge(74,69).
edge(69,118).
edge(118,69).
edge(70,81).
edge(81,70).
edge(70,82).
edge(82,70).
edge(70,83).
edge(83,70).
edge(70,96).
edge(96,70).
edge(70,119).
edge(119,70).
edge(71,95).
edge(95,71).
edge(71,101).
edge(101,71).
edge(71,109).
edge(109,71).
edge(71,110).
edge(110,71).
edge(72,76).
edge(76,72).
edge(72,81).
edge(81,72).
edge(72,82).
edge(82,72).
edge(72,84).
edge(84,72).
edge(72,111).
edge(111,72).
edge(72,117).
edge(117,72).
edge(73,92).
edge(92,73).
edge(73,112).
edge(112,73).
edge(74,92).
edge(92,74).
edge(74,97).
edge(97,74).
edge(74,121).
edge(121,74).
edge(74,123).
edge(123,74).
edge(75,78).
edge(78,75).
edge(75,79).
edge(79,75).
edge(75,86).
edge(86,75).
edge(75,103).
edge(103,75).
edge(75,104).
edge(104,75).
edge(75,107).
edge(107,75).
edge(75,110).
edge(110,75).
edge(75,120).
edge(120,75).
edge(76,80).
edge(80,76).
edge(76,93).
edge(93,76).
edge(76,102).
edge(102,76).
edge(76,103).
edge(103,76).
edge(76,109).
edge(109,76).
edge(77,78).
edge(78,77).
edge(77,85).
edge(85,77).
edge(77,88).
edge(88,77).
edge(77,106).
edge(106,77).
edge(77,107).
edge(107,77).
edge(77,116).
edge(116,77).
edge(77,120).
edge(120,77).
edge(78,81).
edge(81,78).
edge(78,101).
edge(101,78).
edge(78,107).
edge(107,78).
edge(79,88).
edge(88,79).
edge(79,99).
edge(99,79).
edge(79,119).
edge(119,79).
edge(80,88).
edge(88,80).
edge(80,93).
edge(93,80).
edge(80,103).
edge(103,80).
edge(80,113).
edge(113,80).
edge(80,124).
edge(124,80).
edge(81,83).
edge(83,81).
edge(81,92).
edge(92,81).
edge(81,101).
edge(101,81).
edge(81,104).
edge(104,81).
edge(81,114).
edge(114,81).
edge(82,97).
edge(97,82).
edge(82,103).
edge(103,82).
edge(82,120).
edge(120,82).
edge(83,96).
edge(96,83).
edge(83,112).
edge(112,83).
edge(83,121).
edge(121,83).
edge(84,108).
edge(108,84).
edge(84,112).
edge(112,84).
edge(85,95).
edge(95,85).
edge(85,109).
edge(109,85).
edge(85,114).
edge(114,85).
edge(85,117).
edge(117,85).
edge(85,118).
edge(118,85).
edge(85,121).
edge(121,85).
edge(86,91).
edge(91,86).
edge(86,106).
edge(106,86).
edge(87,118).
edge(118,87).
edge(88,90).
edge(90,88).
edge(88,92).
edge(92,88).
edge(88,96).
edge(96,88).
edge(88,101).
edge(101,88).
edge(88,103).
edge(103,88).
edge(88,105).
edge(105,88).
edge(88,118).
edge(118,88).
edge(88,122).
edge(122,88).
edge(89,97).
edge(97,89).
edge(89,98).
edge(98,89).
edge(89,99).
edge(99,89).
edge(89,108).
edge(108,89).
edge(90,96).
edge(96,90).
edge(90,98).
edge(98,90).
edge(90,110).
edge(110,90).
edge(90,125).
edge(125,90).
edge(91,95).
edge(95,91).
edge(91,105).
edge(105,91).
edge(91,109).
edge(109,91).
edge(91,116).
edge(116,91).
edge(91,124).
edge(124,91).
edge(92,93).
edge(93,92).
edge(92,98).
edge(98,92).
edge(92,101).
edge(101,92).
edge(92,102).
edge(102,92).
edge(92,107).
edge(107,92).
edge(92,123).
edge(123,92).
edge(93,102).
edge(102,93).
edge(93,115).
edge(115,93).
edge(93,117).
edge(117,93).
edge(93,118).
edge(118,93).
edge(94,95).
edge(95,94).
edge(94,114).
edge(114,94).
edge(94,121).
edge(121,94).
edge(95,102).
edge(102,95).
edge(95,115).
edge(115,95).
edge(95,117).
edge(117,95).
edge(96,97).
edge(97,96).
edge(96,101).
edge(101,96).
edge(96,112).
edge(112,96).
edge(96,115).
edge(115,96).
edge(97,98).
edge(98,97).
edge(97,100).
edge(100,97).
edge(97,102).
edge(102,97).
edge(97,123).
edge(123,97).
edge(98,110).
edge(110,98).
edge(99,101).
edge(101,99).
edge(99,113).
edge(113,99).
edge(99,119).
edge(119,99).
edge(100,112).
edge(112,100).
edge(100,125).
edge(125,100).
edge(101,102).
edge(102,101).
edge(101,123).
edge(123,101).
edge(101,124).
edge(124,101).
edge(102,104).
edge(104,102).
edge(102,107).
edge(107,102).
edge(102,114).
edge(114,102).
edge(102,122).
edge(122,102).
edge(102,123).
edge(123,102).
edge(103,109).
edge(109,103).
edge(103,112).
edge(112,103).
edge(103,125).
edge(125,103).
edge(104,118).
edge(118,104).
edge(104,121).
edge(121,104).
edge(105,109).
edge(109,105).
edge(105,116).
edge(116,105).
edge(105,123).
edge(123,105).
edge(106,107).
edge(107,106).
edge(106,116).
edge(116,106).
edge(107,108).
edge(108,107).
edge(107,120).
edge(120,107).
edge(109,112).
edge(112,109).
edge(109,114).
edge(114,109).
edge(109,123).
edge(123,109).
edge(110,111).
edge(111,110).
edge(110,113).
edge(113,110).
edge(110,121).
edge(121,110).
edge(111,115).
edge(115,111).
edge(111,117).
edge(117,111).
edge(111,124).
edge(124,111).
edge(112,117).
edge(117,112).
edge(113,116).
edge(116,113).
edge(114,124).
edge(124,114).
edge(115,117).
edge(117,115).
edge(115,118).
edge(118,115).
edge(115,120).
edge(120,115).
edge(115,122).
edge(122,115).
edge(115,125).
edge(125,115).
edge(117,122).
edge(122,117).
edge(118,124).
edge(124,118).
edge(119,123).
edge(123,119).
edge(120,122).
edge(122,120).
edge(121,125).
edge(125,121).
edge(122,125).
edge(125,122).