Karger Min Cut

karger_min_cut.py

"""
The file contains the adjacency list representation of a simple undirected graph.
There are 200 vertices labeled 1 to 200. The first column in the file represents the vertex label,
and the particular row (other entries except the first column) tells all the vertices that the vertex is adjacent to.

So for example, the 6th row looks like : "6	155	56	52	120	......".
This just means that the vertex with label 6 is adjacent to (i.e., shares an edge with) the vertices with labels 155,56,52,120,......,etc

Your task is to code up and run the randomized contraction algorithm for the min cut problem and
use it on the above graph to compute the min cut (i.e., the minimum-possible number of crossing edges).

(HINT: Note that you'll have to figure out an implementation of edge contractions.
Initially, you might want to do this naively, creating a new graph from the old every time there's an edge contraction.
But you should also think about more efficient implementations.)

(WARNING: As per the video lectures, please make sure to run the algorithm many times with different random seeds,
and remember the smallest cut that you ever find.) Write your numeric answer in the space provided.
So e.g., if your answer is 5, just type 5 in the space provided.
"""

import random


def get_two_random_vertices(adjdict):
    """vertices a,b should be distinct"""

    while True:
        a = str(random.randint(1, 200))
        b = str(random.randint(1, 200))
        if a not in adjdict.keys() or b not in adjdict.keys():
            continue
        if a != b:
            break
        else:
            print "Balance of probability, my friend!"

    return a, b


def parse_file():

    with open('kargerMinCut.txt') as fd:
        rows = fd.read().split('\r\n')[0:-1]

        adjdict = {}
        for row in rows:
            ilist = row.split('\t')[0:-1]
            adjdict[ilist[0]] = ilist[1:]

    return adjdict


def collapse_two_vertices(adjdict, a, b):
    adjdict[a] = list(set(adjdict[a] + adjdict[b]) - {b})
    del adjdict[b]


def find_vertices_for_that_edge(adjdict, edge):
    pass


def choose_random_edge_to_contract(adjdict):
    while True:
        # Get a random vertex
        a = str(random.randint(1, 200))
        if a not in adjdict.keys():
            continue

        # Get a random edge
        j = random.randint(0, len(a))

        # Get the connected vertex
        b = a[j]

        if a != b:
            break
        else:
            print "Balance of probability, my friend!"

    return a, b

def find_min_cut(adjdict):

    # Base Case
    if len(adjdict) == 2:
        return adjdict

    edge = choose_random_edge_to_contract(adjdict)

    a, b = find_vertices_for_that_edge(edge)

    # Collapse vertex b onto a
    collapse_two_vertices(adjdict, a, b)

    # Conquer
    return find_min_cut(adjdict)


def main():
    adjdict = parse_file()
    print "{}".format(adjdict)
    outdict = find_min_cut(adjdict)
    print "{}".format(outdict)
    print "Length: {}".format(len(outdict))

if __name__ == "__main__":
    main()

kargerMinCut.txt

1	37	79	164	155	32	87	39	113	15	18	78	175	140	200	4	160	97	191	100	91	20	69	198	196	
2	123	134	10	141	13	12	43	47	3	177	101	179	77	182	117	116	36	103	51	154	162	128	30	
3	48	123	134	109	41	17	159	49	136	16	130	141	29	176	2	190	66	153	157	70	114	65	173	104	194	54	
4	91	171	118	125	158	76	107	18	73	140	42	193	127	100	84	121	60	81	99	80	150	55	1	35	23	93	
5	193	156	102	118	175	39	124	119	19	99	160	75	20	112	37	23	145	135	146	73	35	
6	155	56	52	120	131	160	124	119	14	196	144	25	75	76	166	35	87	26	20	32	23	
7	156	185	178	79	27	52	144	107	78	22	71	26	31	15	56	76	112	39	8	113	93	
8	185	155	171	178	108	64	164	53	140	25	100	133	9	52	191	46	20	150	144	39	62	131	42	119	127	31	7	
9	91	155	8	160	107	132	195	26	20	133	39	76	100	78	122	127	38	156	191	196	115	
10	190	184	154	49	2	182	173	170	161	47	189	101	153	50	30	109	177	148	179	16	163	116	13	90	185	
11	123	134	163	41	12	28	130	13	101	83	77	109	114	21	82	88	74	24	94	48	33	
12	161	109	169	21	24	36	65	50	2	101	159	148	54	192	88	47	11	142	43	70	182	177	179	189	194	33	
13	161	141	157	44	83	90	181	41	2	176	10	29	116	134	182	170	165	173	190	159	47	82	111	142	72	154	110	21	103	130	11	33	138	152	
14	91	156	58	122	62	113	107	73	137	25	19	40	6	139	150	46	37	76	39	127	
15	149	58	68	52	39	67	121	191	1	45	100	18	118	174	40	85	196	122	42	193	119	139	26	127	145	135	57	38	7	
16	48	10	36	187	43	3	114	173	111	142	129	88	189	117	128	147	141	194	180	106	167	179	66	74	136	51	59	
17	48	123	134	36	163	3	44	117	167	161	152	95	170	83	180	77	65	72	109	47	43	88	159	197	28	194	181	49	
18	193	149	56	62	15	160	67	191	140	52	178	96	107	132	1	145	89	198	4	26	73	151	126	34	115	
19	156	80	178	164	108	84	71	174	40	62	113	22	89	45	91	126	195	144	5	14	172	
20	185	122	171	56	8	52	73	191	67	126	9	119	1	89	79	107	96	31	75	55	5	6	34	23	
21	188	187	12	173	180	197	138	167	63	111	95	13	192	116	94	114	105	49	177	51	130	90	11	50	66	157	176	
22	156	27	32	131	7	56	53	81	149	23	100	146	115	26	175	121	96	75	57	39	119	71	132	19	150	140	93	
23	91	122	124	22	200	195	145	5	69	125	55	68	156	20	58	191	4	57	149	6	
24	123	134	161	163	169	72	116	167	30	33	77	162	143	159	187	63	184	130	28	50	153	12	148	11	53	
25	193	185	79	108	8	158	87	73	81	115	39	64	178	132	27	68	127	84	14	52	200	97	6	93	
26	193	58	27	108	52	144	160	18	84	81	22	75	139	166	15	107	198	131	7	9	133	6	
27	156	139	144	166	112	100	26	174	31	42	75	158	122	81	22	7	58	73	89	115	39	25	200	69	169	
28	134	188	24	184	159	29	72	114	152	116	169	173	141	17	111	61	192	90	11	177	179	77	33	66	83	136	
29	48	134	188	13	47	88	3	82	92	28	194	50	192	189	123	199	177	147	43	106	148	197	77	103	129	181	
30	165	123	10	24	41	187	47	168	92	148	197	101	50	2	179	111	130	77	153	199	70	
31	27	171	56	131	146	139	191	89	20	108	38	71	75	69	196	149	97	8	86	98	7	
32	156	149	171	62	22	185	35	124	56	38	158	97	53	121	160	1	191	58	89	127	87	120	39	99	84	60	151	174	6	
33	48	161	109	141	24	187	47	88	168	183	110	103	95	116	28	12	11	13	83	134	63	
34	37	122	171	118	76	131	166	137	40	46	97	87	80	164	127	18	62	52	20	139	
35	79	164	125	32	107	137	75	121	85	55	69	45	193	132	4	5	200	135	76	139	198	6	
36	165	188	17	106	88	16	177	110	147	154	159	179	136	41	50	141	66	162	152	168	184	12	43	72	180	190	77	2	170	61	122	
37	193	149	39	121	191	115	146	52	127	79	198	58	125	38	34	1	76	89	164	97	86	178	108	87	84	124	98	174	195	14	5	57	196	186	
38	193	37	86	32	76	107	73	85	127	100	46	89	31	57	96	158	99	160	45	15	9	
39	193	37	122	102	8	158	32	87	85	81	200	60	5	27	155	1	58	150	15	113	76	84	22	25	151	139	100	14	145	9	7	
40	91	156	122	79	118	125	52	175	87	15	81	166	132	121	19	14	160	34	78	71	
41	36	169	184	116	163	106	189	11	104	61	30	123	129	111	3	47	49	154	161	152	13	153	65	92	183	177	162	95	54	70	108	
42	178	79	27	53	171	164	102	52	87	113	15	191	131	91	62	193	8	122	89	56	4	127	145	112	
43	165	161	12	70	199	54	17	190	16	153	141	36	47	44	194	110	82	189	2	148	183	29	130	94	170	51	61	59	
44	188	163	169	17	13	43	114	173	142	154	103	129	181	105	157	148	182	101	110	66	176	49	
45	156	80	149	58	178	53	108	68	56	125	15	93	75	135	174	198	81	166	113	100	19	89	35	97	38	
46	193	58	86	122	155	8	175	160	99	127	67	14	150	144	126	146	34	131	55	38	196	
47	123	10	109	41	17	12	43	116	59	33	13	2	187	165	88	117	29	30	176	147	180	101	130	194	50	94	152	70	
48	180	128	188	197	105	51	94	190	116	29	183	114	153	33	16	49	3	63	184	17	141	168	179	162	11	66	83	193	
49	48	123	10	186	141	41	168	3	148	142	179	21	136	109	44	117	17	103	187	74	
50	165	123	10	188	36	169	24	187	12	65	29	167	47	21	134	130	111	168	77	116	138	106	66	30	
51	165	48	109	141	163	159	92	190	143	2	21	138	43	59	192	117	16	184	104	169	
52	37	178	8	6	15	200	133	80	102	96	40	119	164	166	127	151	20	42	7	26	76	18	73	99	78	25	132	139	191	150	34	
53	156	122	102	193	137	133	42	62	45	64	60	78	160	132	155	56	144	131	196	178	125	8	32	113	22	98	121	198	24	
54	123	187	12	43	168	65	129	130	147	95	41	61	59	141	3	138	114	199	66	110	
55	68	56	125	113	73	78	200	46	131	85	107	89	185	60	84	4	35	99	171	71	20	23	
56	193	122	53	108	45	55	18	125	86	171	79	6	85	133	80	140	96	31	107	20	32	87	120	42	73	84	22	112	196	7	
57	79	155	158	76	84	22	75	121	85	191	100	97	15	37	102	69	38	64	195	145	23	
58	15	146	107	193	140	84	144	86	14	150	26	60	46	166	80	87	139	195	126	45	37	27	102	62	32	175	39	124	23	93	188	
59	186	163	187	47	168	92	143	147	157	54	51	61	199	43	103	63	184	16	188	197	
60	58	86	178	53	171	125	39	144	146	73	124	4	93	32	99	158	132	80	91	96	75	174	55	196	
61	188	116	41	114	183	28	77	54	36	163	187	147	179	65	63	190	43	186	59	189	
62	193	185	79	53	171	102	146	84	198	14	58	137	8	166	175	32	113	18	115	196	42	200	132	121	19	112	133	172	34	
63	48	24	116	183	111	167	21	162	90	181	147	105	106	101	33	123	153	184	128	168	61	59	
64	91	149	122	53	8	120	113	124	119	25	132	131	193	121	144	68	185	108	175	107	57	
65	186	17	12	114	82	3	66	159	167	197	50	101	176	94	54	134	41	165	157	194	180	77	103	74	61	
66	188	36	116	3	65	183	72	180	77	16	136	177	82	159	28	95	48	50	187	21	44	54	176	
67	91	156	102	68	175	131	144	15	18	146	119	20	200	46	112	139	75	80	86	137	
68	122	171	55	78	175	96	75	71	93	118	195	115	67	79	45	158	15	120	155	193	87	146	81	25	64	23	
69	91	108	125	131	81	75	85	174	145	89	27	200	35	156	1	98	86	23	191	127	31	57	
70	165	123	163	153	12	43	168	3	114	82	148	190	129	74	176	47	110	181	41	30	
71	193	79	171	68	124	98	120	73	75	93	151	108	89	155	19	96	22	119	7	125	85	127	40	55	140	31	
72	109	169	24	116	17	114	182	190	141	186	192	28	104	13	66	165	162	36	159	77	110	129	130	181	
73	91	80	27	160	4	20	100	56	193	60	38	18	25	172	76	14	55	52	149	96	78	71	195	127	5	112	97	93	
74	88	104	197	111	130	95	11	138	123	77	159	65	179	94	165	70	141	16	153	136	83	49	
75	91	79	27	171	68	158	87	81	22	119	71	166	57	60	35	160	69	175	26	193	45	127	67	126	89	20	5	31	198	6	
76	37	178	175	120	122	57	52	34	4	156	98	115	133	131	171	149	85	38	174	39	73	99	14	140	35	135	172	9	7	6	
77	24	116	17	72	190	110	36	173	143	94	65	29	61	154	2	161	90	66	159	28	128	117	11	50	138	74	30	
78	156	80	53	164	68	131	144	107	73	195	55	175	1	126	7	149	171	81	91	52	124	40	9	
79	80	37	158	40	75	108	198	25	62	42	7	86	57	102	122	145	175	71	1	35	164	68	118	56	144	200	139	20	112	135	172	163	
80	91	144	100	118	45	78	139	112	149	98	113	87	195	124	85	73	119	19	79	99	58	56	52	146	81	4	60	137	67	126	145	97	34	134	
81	86	27	120	39	131	40	132	25	69	96	26	127	108	75	68	135	98	80	115	149	78	22	4	45	172	
82	161	186	109	153	43	159	114	101	104	70	29	197	192	116	148	65	152	184	13	154	92	110	130	11	147	66	176	
83	17	13	153	88	111	90	117	95	11	33	147	28	109	199	48	74	167	182	154	101	
84	149	58	86	178	171	62	175	113	26	135	96	198	39	19	57	144	37	118	32	56	119	4	98	25	200	150	55	
85	156	80	185	155	102	56	158	39	76	15	69	38	150	175	118	137	71	35	120	57	55	135	
86	58	84	120	81	112	37	60	46	185	193	38	125	118	175	149	99	108	126	133	102	79	56	144	67	69	31	109	
87	80	149	58	118	25	75	126	115	68	178	37	200	32	40	164	56	42	193	107	1	39	113	145	89	172	6	34	93	
88	36	116	12	47	165	168	29	83	159	154	74	148	92	176	180	33	110	194	167	17	114	173	16	11	
89	37	27	102	32	42	18	99	71	151	19	55	75	98	131	69	45	31	38	195	87	20	135	115	
90	163	116	13	173	28	110	190	77	129	117	130	10	179	92	134	194	21	63	83	157	94	152	199	
91	126	14	75	135	107	80	102	67	160	158	144	23	64	155	4	198	40	9	73	69	193	185	149	164	42	78	60	98	19	1	165	
92	161	109	163	187	88	186	141	51	117	197	59	173	192	82	29	143	116	41	30	111	148	129	90	194	152	170	
93	68	99	71	60	45	150	145	98	25	87	122	178	185	7	144	4	22	73	58	112	
94	48	163	65	173	182	154	77	21	117	11	147	74	189	43	114	47	177	192	104	90	
95	123	141	169	17	168	114	179	21	33	165	167	177	41	103	83	199	129	182	188	74	66	157	152	54	176	
96	171	164	68	56	52	18	73	84	81	124	22	71	60	126	150	20	97	38	149	158	196	115	
97	185	149	37	178	122	108	118	32	131	1	31	140	73	34	45	25	80	133	57	96	
98	80	171	164	158	120	76	99	81	71	37	91	151	144	172	140	150	160	121	84	53	139	89	69	31	133	93	
99	80	86	178	122	118	125	52	193	32	174	46	113	98	93	89	150	102	76	100	124	4	60	55	5	38	196	
100	80	185	149	27	8	113	131	15	73	99	22	4	200	45	102	172	57	164	38	39	1	112	9	
101	165	10	188	109	141	163	187	12	168	82	65	148	180	47	167	2	162	169	192	30	179	11	44	83	170	63	
102	91	86	79	53	171	155	67	113	39	137	158	196	166	120	42	89	58	5	119	85	62	52	146	99	121	100	57	
103	161	188	186	184	153	159	167	189	2	168	13	29	104	142	33	65	197	117	148	44	95	181	59	49	
104	134	188	186	141	184	41	187	168	114	82	148	192	194	154	74	3	190	161	105	163	72	103	94	170	51	
105	165	48	161	116	159	104	21	129	63	44	169	106	142	190	181	143	179	157	173	188	199	176	
106	36	163	169	184	41	159	29	197	111	16	179	162	105	138	148	50	165	63	173	109	
107	91	58	56	125	158	87	191	133	9	38	122	164	175	135	4	35	14	7	185	78	18	146	151	26	64	126	55	20	112	198	172	
108	86	178	79	164	37	25	195	144	120	198	26	56	19	132	69	193	115	45	172	97	155	8	81	71	166	139	174	64	31	41	
109	10	47	116	12	128	51	167	180	179	33	123	101	142	92	143	199	154	3	72	82	141	17	168	114	173	183	148	189	11	181	106	83	152	49	86	
110	165	186	36	163	169	43	88	168	33	138	147	13	167	189	184	134	72	90	188	82	77	44	54	70	
111	41	92	114	162	188	129	187	170	152	83	142	74	157	16	13	138	186	106	63	184	28	21	50	30	192	
112	193	80	86	27	137	174	67	5	79	198	132	127	42	131	100	73	107	56	135	62	7	93	
113	156	80	149	171	102	62	39	133	84	87	198	1	53	64	55	172	122	100	42	14	160	99	124	137	45	19	145	7	
114	48	104	136	16	61	72	181	128	82	88	138	109	129	70	192	3	153	65	95	44	111	28	21	11	94	54	
115	185	37	27	108	68	62	87	120	76	81	22	25	151	139	191	140	9	89	96	18	
116	48	188	109	24	157	61	41	181	128	66	88	63	152	189	168	90	105	72	77	10	13	47	82	173	92	142	28	180	2	21	117	50	33	136	164	
117	17	47	92	16	179	2	103	90	194	189	192	94	143	170	162	83	116	129	184	77	138	152	51	49	
118	193	156	80	86	155	68	196	145	40	4	97	79	5	99	87	149	174	34	137	166	131	15	160	84	121	85	
119	80	178	102	52	160	124	84	185	6	22	67	174	8	121	133	5	75	64	15	150	71	151	145	20	
120	185	86	171	108	102	68	200	193	126	64	160	32	150	6	115	98	81	56	191	76	124	71	139	85	195	135	
121	156	185	37	32	15	146	22	119	4	98	151	57	62	126	53	139	40	102	35	118	64	135	133	
122	156	146	23	99	196	46	14	56	53	175	164	20	68	39	195	126	97	40	34	64	79	27	155	113	76	131	15	42	107	166	151	9	93	36	
123	165	194	50	70	95	11	153	30	24	17	49	47	54	2	189	147	199	3	188	197	186	109	41	29	129	130	128	74	136	63	156	
124	193	80	125	32	146	99	23	5	60	113	120	191	6	58	64	119	71	37	78	96	137	
125	37	86	56	4	133	69	178	132	53	172	45	60	151	40	198	55	35	107	99	124	71	137	127	23	
126	91	58	86	122	155	87	120	146	78	200	121	19	80	20	137	75	96	107	18	156	46	135	
127	37	178	32	52	131	160	81	4	25	191	125	38	71	15	8	42	75	46	174	73	14	69	112	172	9	34	
128	48	134	161	109	116	187	114	183	16	179	189	130	181	142	123	138	2	136	77	152	63	
129	165	184	41	153	114	148	111	177	16	180	44	29	123	54	173	72	92	70	199	105	90	117	95	157	
130	186	169	24	3	154	189	21	136	72	82	74	190	11	47	13	173	54	181	43	123	90	128	50	138	30	176	
131	193	53	76	78	22	69	97	118	178	122	140	81	34	164	8	100	127	67	31	6	42	146	200	195	26	64	46	55	89	112	
132	185	149	53	171	108	125	18	81	60	25	139	191	178	64	52	9	62	22	40	164	35	112	
133	86	53	56	125	8	52	113	76	107	119	195	97	156	98	121	62	140	26	175	9	
134	153	11	17	182	165	197	138	173	24	28	104	128	29	2	167	152	183	3	162	154	186	13	65	142	110	90	50	33	157	80	
135	91	171	164	107	84	81	45	5	35	112	120	15	151	85	76	79	178	121	126	89	
136	165	36	187	3	114	173	190	130	128	66	74	152	123	154	116	28	49	153	16	169	
137	156	185	53	155	102	118	62	166	175	200	151	112	113	14	124	80	146	35	125	34	85	67	126	145	172	
138	134	186	153	114	111	142	110	179	21	128	130	117	197	169	77	13	74	51	180	50	106	54	
139	80	58	27	164	132	121	108	115	140	31	79	98	15	160	52	26	171	39	195	120	67	14	35	196	34	
140	185	58	56	8	175	131	144	18	4	166	98	139	1	195	22	156	71	76	178	115	97	133	
141	109	104	184	2	143	188	51	49	33	197	48	176	95	159	148	101	154	13	170	190	36	43	3	92	72	16	28	167	180	147	74	54	178	
142	161	109	169	12	183	111	163	187	162	180	16	165	116	184	138	44	13	49	134	143	177	103	128	181	105	192	
143	165	161	109	141	24	184	168	92	142	154	180	51	147	179	176	183	189	59	159	167	77	117	105	152	
144	91	80	58	178	27	53	164	108	8	158	60	79	67	155	78	140	7	86	26	174	84	98	64	19	46	145	6	93	
145	178	79	155	118	18	151	69	39	113	42	119	93	80	144	87	15	137	23	158	166	5	57	172	
146	149	58	37	122	62	60	68	107	31	67	172	195	121	131	102	185	174	124	126	80	22	137	46	5	
147	123	186	36	47	183	29	182	197	16	167	110	143	168	83	82	141	63	94	54	59	157	170	61	
148	10	188	186	141	163	12	43	88	82	109	192	70	161	30	129	24	92	49	177	29	104	197	154	101	103	162	181	106	44	176	
149	156	80	200	146	15	185	87	91	100	45	37	178	18	32	64	132	97	84	150	113	86	118	76	73	81	78	22	31	96	23	161	
150	149	58	8	175	120	39	99	119	166	98	200	85	14	4	46	96	84	22	93	52	
151	125	52	160	71	166	98	137	145	122	171	119	193	175	32	121	107	115	18	39	89	135	196	
152	134	161	36	116	41	17	82	111	28	128	157	13	92	47	143	117	109	90	95	136	170	
153	165	48	123	134	10	186	138	187	103	82	70	163	129	188	170	173	24	83	167	41	43	3	114	154	180	74	136	63	30	
154	134	10	109	141	36	41	88	159	82	104	143	148	197	44	13	94	130	162	177	153	167	77	2	83	136	170	
155	91	185	53	164	108	145	171	200	6	122	8	9	85	57	1	137	126	102	118	46	68	158	39	144	160	71	172	
156	7	53	113	45	14	193	122	40	67	19	121	22	118	78	5	137	166	149	32	85	178	27	158	76	126	140	69	133	9	23	123	
157	184	116	13	3	65	111	90	105	187	147	152	134	59	95	186	197	44	170	129	21	
158	91	193	79	27	102	68	32	75	156	107	185	144	4	57	39	155	98	171	85	25	175	60	145	38	96	
159	188	141	36	24	13	12	88	103	105	179	177	17	3	182	51	82	28	161	154	106	65	183	72	143	77	66	74	
160	91	185	53	32	120	155	6	9	18	127	171	118	113	119	151	26	46	195	200	73	98	75	139	40	1	5	198	38	
161	165	10	24	173	142	182	162	92	13	152	33	82	189	43	143	128	103	186	105	12	188	184	41	17	159	148	104	180	77	194	170	149	
162	134	161	188	186	36	24	173	182	111	142	72	154	101	48	148	2	179	106	63	41	117	
163	177	92	10	148	101	44	169	59	110	188	17	51	90	186	94	11	24	70	106	182	41	153	187	104	142	190	61	79	
164	185	37	122	175	139	144	91	35	19	96	98	78	155	1	108	198	42	135	79	195	8	52	87	131	107	166	132	100	34	116	
165	30	105	36	101	167	183	43	50	70	189	181	190	161	123	136	51	143	129	153	110	134	169	13	47	88	65	142	72	95	106	74	91	
166	156	58	27	102	118	62	52	191	140	164	40	122	151	108	75	174	137	196	150	34	200	45	26	145	6	
167	165	134	109	24	17	153	187	88	168	65	182	177	154	16	194	141	103	50	147	63	110	101	179	143	21	95	83	
168	36	169	116	88	48	70	30	33	101	104	109	110	143	181	167	54	199	49	59	95	177	180	103	50	147	63	
169	163	50	184	12	176	106	41	194	173	168	110	142	44	95	130	24	165	182	72	177	197	28	101	138	105	136	51	27	
170	10	186	141	17	13	153	111	117	157	92	161	152	147	104	179	154	43	101	36	199	
171	34	60	68	31	20	42	62	4	120	71	32	135	113	175	84	102	132	96	98	75	155	56	8	158	76	160	78	151	139	55	184	
172	185	108	125	113	146	73	98	174	100	155	81	79	76	127	87	137	107	19	62	145	
173	134	10	161	169	13	153	109	162	44	21	88	182	3	190	179	136	90	16	116	94	92	28	77	129	130	105	106	
174	27	118	175	76	144	15	146	99	119	166	45	32	19	172	191	60	108	37	69	112	127	
175	86	122	79	171	164	68	62	84	140	5	40	196	46	174	150	67	58	76	193	158	107	78	22	137	75	151	85	195	64	1	133	
176	141	169	13	47	88	3	65	183	177	143	148	82	105	130	66	181	44	21	182	95	70	
177	10	36	163	169	159	29	148	190	12	199	167	176	180	2	192	168	142	41	179	129	154	28	21	95	66	94	
178	149	76	19	52	127	108	45	156	60	198	99	37	144	7	97	145	84	119	42	191	53	125	8	87	131	18	25	132	195	140	135	93	141	
179	10	109	36	159	173	177	49	117	12	48	101	189	2	138	128	95	106	28	167	16	143	162	90	105	74	170	199	30	61	
180	48	109	17	88	142	177	16	65	194	36	153	116	161	66	143	141	129	47	168	21	101	181	138	
181	165	188	184	116	13	168	114	182	130	128	44	103	148	63	29	142	180	17	109	72	105	176	70	
182	134	10	161	163	169	184	13	159	173	183	147	189	162	181	12	72	167	94	199	192	2	95	44	83	176	
183	165	48	134	188	186	63	33	147	43	61	109	142	159	66	41	128	182	176	190	184	143	189	
184	48	10	141	169	24	143	41	161	181	36	129	197	104	186	182	28	106	157	103	199	82	183	111	142	110	117	63	51	59	171	
185	193	140	8	97	7	121	160	155	85	172	91	100	164	132	25	120	20	62	137	115	149	86	32	158	107	146	119	64	55	93	10	
186	161	104	199	162	148	110	138	183	153	103	192	82	130	123	59	49	147	134	65	170	163	184	187	92	197	111	72	157	61	37	
187	24	153	186	92	189	54	33	59	21	167	163	101	136	50	197	16	104	128	192	30	47	111	142	66	157	61	49	
188	48	123	50	104	36	101	148	66	161	44	28	21	162	116	183	103	159	181	61	29	141	163	153	111	110	190	95	105	59	58	
189	165	123	10	161	116	41	187	43	29	182	197	16	110	179	143	12	183	103	199	109	130	128	194	117	94	61	
190	165	48	10	141	13	43	3	173	183	104	177	72	36	77	188	90	136	51	163	70	130	105	61	
191	193	37	178	8	32	120	15	42	107	18	124	166	132	174	20	52	57	31	115	127	1	69	9	23	
192	186	187	12	114	82	92	29	148	104	182	177	72	28	101	21	117	94	51	111	142	
193	26	112	191	62	195	25	91	39	71	158	131	46	5	38	37	185	18	118	124	56	156	58	86	53	108	68	175	87	120	15	42	73	99	4	75	151	64	35	48	
194	123	169	43	88	65	29	104	16	167	180	90	189	161	199	47	92	3	12	17	117	
195	193	80	58	122	164	108	68	160	146	78	139	23	120	178	133	73	175	37	131	9	19	89	140	57	
196	122	53	102	118	62	175	15	166	31	9	37	6	99	151	56	139	46	1	96	60	
197	48	123	134	141	184	187	82	65	92	106	148	147	199	29	17	30	189	186	74	169	154	21	103	138	157	59	
198	91	37	178	79	164	108	125	62	113	18	84	45	26	112	35	107	160	53	1	75	
199	123	186	109	184	43	168	29	182	197	177	189	129	194	95	83	170	54	105	90	179	30	59	
200	149	155	52	87	120	39	160	137	27	79	131	100	25	55	23	126	84	166	150	62	67	1	69	35