In [ ]:

```
# Run this cell
%config InteractiveShell.ast_node_interactivity="none"
%pip install networkx
import networkx as nx
import warnings
import base64
warnings.simplefilter(action='ignore', category=FutureWarning)
def f(globals, locals):
import base64
CODE = ("ZGVmIG1ha2VfcHJpbnRfbG9jYWxzKCk6IAogICAgIyBJbiBhIGZ1bmN0aW9uIHRvIHByZXZlbnQgbG9jYWxzIGFuZCBpbXBvcnRzIGZyb20gbGVha2luZy4KICAgIGdsb2JhbCBtYWtlX3ByaW50X2xvY2FscwogICAgZGVsIG1ha2VfcHJpbnRfbG9jYWxzICAjIE9ubHkgcnVuIHRoaXMgZnVuY3Rpb24gb25jZS4KCiAgICBpbXBvcnQgSVB5dGhvbgogICAgaW1wb3J0IGFzdAogICAgaW1wb3J0IGluc3BlY3QKCiAgICBjbGFzcyBWaXNpdG9yKGFzdC5Ob2RlVmlzaXRvcik6CiAgICAgICAgZGVmIF9faW5pdF9fKHNlbGYpOgogICAgICAgICAgICBzZWxmLnZhcmlhYmxlcyA9IHNldCgpCiAgICAgICAgZGVmIHZpc2l0X05hbWUoc2VsZiwgbmFtZSk6CiAgICAgICAgICAgIHNlbGYudmFyaWFibGVzLmFkZChuYW1lLmlkKQogICAgICAgICMgVE9ETzogUG9zc2libHkgZGV0ZWN0IHdoZXRoZXIgdmFyaWFibGVzIGFyZSBhc3NpZ25lZCB0by4KCiAgICBBTExPV19UWVBFUyA9IFtpbnQsIGZsb2F0LCBzdHIsIGJvb2wsIGxpc3QsIGRpY3QsIHR1cGxlLCByYW5nZV0KICAgIGRlZiBmaWx0ZXJfdmFyaWFibGVzKHZhcmlhYmxlcywgbG9jYWxzKToKICAgICAgICBmb3IgdiBpbiB2YXJpYWJsZXM6CiAgICAgICAgICAgIGlmIHYgaW4gbG9jYWxzIGFuZCB0eXBlKGxvY2Fsc1t2XSkgaW4gQUxMT1dfVFlQRVM6CiAgICAgICAgICAgICAgICB5aWVsZCB2CiAgCiAgICAjIFVuZm9ydHVuYXRlbHksIHRoZXJlIGRvZXNuJ3Qgc2VlbSB0byBiZSBhIHN1cHBvcnRlZCB3YXkgb2YgZ2V0dGluZwogICAgIyB0aGUgY3VycmVudCBjZWxsJ3MgY29kZSB2aWEgdGhlIHB1YmxpYyBJUHl0aG9uIEFQSXMuIEhvd2V2ZXIsIGJlY2F1c2UKICAgICMgd2UgYXJlIGdldHRpbmcgY2FsbGVkIGZyb20gSVB5dGhvbiBpdHNlbGYgYW5kIHdlIGFyZSBhbHJlYWR5IGluc3BlY3RpbmcKICAgICMgdGhlIHN0YWNrdHJhY2UsIHdlIG1pZ2h0IGFzIHdlbGwganVzdCBwZWVrIGludG8gaXRzIGZyYW1lLi4uCiAgICBpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI1LjUuMCI6CiAgICAgICAgIyBjb2xhYgogICAgICAgIGRlZiBnZXRfYXN0KGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGFzdC5Nb2R1bGUoZnJhbWUuZl9iYWNrLmZfYmFjay5mX2xvY2Fsc1sibm9kZWxpc3QiXSkKICAgICAgICBkZWYgZmluZF9sb2NhbHMoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gZnJhbWUuZl9sb2NhbHMKICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfYmFjay5mX2NvZGUuY29fZmlsZW5hbWUuZW5kc3dpdGgoIklQeXRob24vY29yZS9pbnRlcmFjdGl2ZXNoZWxsLnB5IikKCiAgICBlbGlmIElQeXRob24uX192ZXJzaW9uX18gPT0gIjguNC4wIjoKICAgICAgICAjIGxhYiBjb21wdXRlcnMKICAgICAgICBkZWYgZ2V0X2FzdChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBhc3QuTW9kdWxlKGZyYW1lLmZfYmFjay5mX2JhY2suZl9sb2NhbHNbIm5vZGVsaXN0Il0pCiAgICAgICAgZGVmIGZpbmRfbG9jYWxzKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfbG9jYWxzCiAgICAgICAgZGVmIGF0X3RvcF9sZXZlbChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9jb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpCiAgICBlbHNlOgogICAgICAgIHByaW50KGYicHJpbnRfbG9jYWxzKCkgbm90IHN1cHBvcnRlZCBvbiBJUHl0aG9uIHZlcnNpb24ge0lQeXRob24uX192ZXJzaW9uX199IikKCiAgICBkZWYgZ2V0X2NlbGxfbmFtZXMoZnJhbWUpOgogICAgICAgIHRyZWUgPSBnZXRfYXN0KGZyYW1lKQogICAgICAgIHZpc2l0b3IgPSBWaXNpdG9yKCkKICAgICAgICB2aXNpdG9yLnZpc2l0KHRyZWUpCiAgICAgICAgcmV0dXJuIGZpbHRlcl92YXJpYWJsZXModmlzaXRvci52YXJpYWJsZXMsIGZyYW1lLmZfbG9jYWxzKQoKICAgIGRlZiBmaW5kX3doaWNoKGZyYW1lKToKICAgICAgICAjIEZyYW1lIGlzIHRoZSBmcmFtZSB3aG9zZSBsb2NhbHMgd2UgYXJlIGludGVyZXN0ZWQgaW4gcHJpbnRpbmcuCiAgICAgICAgaWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgIyBUaGUgcGFyZW50IGZyYW1lIG9mIHRoZSBpbnRlcmVzdGVkIGZyYW1lIGlzIGEgbW9kdWxlLCBtb3N0IGxpa2VseQogICAgICAgICAgICAjICJpbnRlcmFjdGl2ZXNoZWxsIi4gVGhpcyBtZWFucyB3ZSBhcmUgaW4gdGhlIGdsb2JhbCBzY29wZSwgc2luY2UKICAgICAgICAgICAgIyBvbmx5IHRoZSBnbG9iYWwgc2NvcGUgc2hvdWxkIGJlIGRpcmVjdGx5IHJ1biBieSB0aGUgaW50ZXJhY3RpdmUgc2hlbGwuCiAgICAgICAgICAgIHJldHVybiBzZXQoZ2V0X2NlbGxfbmFtZXMoZnJhbWUpKQogICAgICAgICMgVGhlIHBhcmVudCBmcmFtZSBpcyBub3QgYSBtb2R1bGUsIHNvIHdlIGFyZSBpbiBhIGxvY2FsIHNjb3BlLgogICAgICAgIHJldHVybiBzZXQoZnJhbWUuZl9sb2NhbHMpCgogICAgZGVmIHByaW50X2xvY2Fscygqd2hpY2gsIHR5cGVzPUZhbHNlKToKICAgICAgICAiIiJQcmludCB0aGUgbG9jYWwgdmFyaWFibGVzIGluIHRoZSBjYWxsZXIncyBmcmFtZS4iIiIKICAgICAgICBpbXBvcnQgaW5zcGVjdAogICAgICAgICMgY3VycmVudGZyYW1lKCkgZnJhbWUgaXMgcHJpbnRfbG9jYWxzLiBXZSB3YW50IHRoZSBjYWxsZXIncyBmcmFtZQogICAgICAgIGZyYW1lID0gaW5zcGVjdC5jdXJyZW50ZnJhbWUoKS5mX2JhY2sKICAgICAgICBsb2NhbHMgPSBmaW5kX2xvY2FscyhmcmFtZSkKICAgICAgICB3aGljaCA9IHNldCh3aGljaCkgaWYgd2hpY2ggZWxzZSBmaW5kX3doaWNoKGZyYW1lKQogICAgICAgIGxsID0ge2s6IHYgZm9yIGssIHYgaW4gbG9jYWxzLml0ZW1zKCkgaWYgayBpbiB3aGljaH0KICAgICAgICBpZiBub3QgbGw6CiAgICAgICAgICAgIHByaW50KCJwcmludF9sb2NhbHM6IG5vIGxvY2FscyIpCiAgICAgICAgICAgIHJldHVybgogICAgICAgIGlmIHR5cGVzOgogICAgICAgICAgICBwcmludCgiXG4iLmpvaW4oZiJ7a306IHt0eXBlKHYpLl9fbmFtZV9ffSDihpAge3Z9IiBmb3IgaywgdiBpbiBsbC5pdGVtcygpKSkKICAgICAgICBlbHNlOgogICAgICAgICAgICBwcmludCgiOyAiLmpvaW4oZiJ7a30g4oaQIHtyZXByKHYpfSIgZm9yIGssIHYgaW4gbGwuaXRlbXMoKSkpCgogICAgcmV0dXJuIHByaW50X2xvY2FscwoKcHJpbnRfbG9jYWxzID0gbWFrZV9wcmludF9sb2NhbHMoKQ==", "ZGVmIG1ha2VfcHJldHR5X2Fzc2VydCgpOgogICAgaW1wb3J0IHN5cwogICAgaW1wb3J0IElQeXRob24KICAgIGltcG9ydCBhc3QKICAgIGltcG9ydCBpbnNwZWN0CiAgICBpbXBvcnQgaW8KICAgIGltcG9ydCBpdGVydG9vbHMKICAgIAogICAgZ2xvYmFsIG1ha2VfcHJldHR5X2Fzc2VydAogICAgZGVsIG1ha2VfcHJldHR5X2Fzc2VydAoKICAgIGlmIElQeXRob24uX192ZXJzaW9uX18gPT0gIjUuNS4wIjoKICAgICAgICAjIGNvbGFiIFRPRE8KICAgICAgICBkZWYgZ2V0X2Fzc2VydF9saW5lKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfYmFjay5mX2JhY2suZl9sb2NhbHNbIm5vZGUiXQogICAgICAgIGRlZiBhdF90b3BfbGV2ZWwoZnJhbWUpOgogICAgICAgICAgICBjb2RlID0gZnJhbWUuZl9iYWNrLmZfYmFjay5mX2NvZGUKICAgICAgICAgICAgcmV0dXJuIGNvZGUuY29fZmlsZW5hbWUuZW5kc3dpdGgoIklQeXRob24vY29yZS9pbnRlcmFjdGl2ZXNoZWxsLnB5IikKICAgICAgICBkZWYgY2FuX2Fubm90YXRlKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIEZhbHNlCgogICAgZWxpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI4LjQuMCI6CiAgICAgICAgIyBsYWIgY29tcHV0ZXJzCiAgICAgICAgZGVmIGdldF9hc3NlcnRfbGluZShmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9iYWNrLmZfbG9jYWxzWyJub2RlIl0KICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgY29kZSA9IGZyYW1lLmZfYmFjay5mX2JhY2suZl9jb2RlCiAgICAgICAgICAgIHJldHVybiBjb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpIGFuZCBjb2RlLmNvX25hbWUgPT0gInJ1bl9hc3Rfbm9kZXMiCiAgICAgICAgZGVmIGNhbl9hbm5vdGF0ZShmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBhdF90b3BfbGV2ZWwoZnJhbWUpIGFuZCBGYWxzZQoKICAgIGRlZiBpc19saXRlcmFsKGEpOgogICAgICAgIHRyeToKICAgICAgICAgICAgYXN0LmxpdGVyYWxfZXZhbChhKQogICAgICAgICAgICByZXR1cm4gVHJ1ZQogICAgICAgIGV4Y2VwdCBWYWx1ZUVycm9yOgogICAgICAgICAgICByZXR1cm4gRmFsc2UKICAgICAgICByZXR1cm4gRmFsc2UKCgogICAgZGVmIGFubm90YXRlX2NhbGwoZnJhbWUpOgogICAgICAgIGlmIG5vdCBjYW5fYW5ub3RhdGUoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4KICAgICAgICAKICAgICAgICBleHByOiBhc3QuRXhwciA9IGdldF9hc3NlcnRfbGluZShmcmFtZSkKICAgICAgICBmb3Iga3dhcmcgaW4gZXhwci52YWx1ZS5rZXl3b3JkczoKICAgICAgICAgICAgaWYga3dhcmcuYXJnID09ICJnb3QiOgogICAgICAgICAgICAgICAgZ290ID0ga3dhcmcudmFsdWUKCiAgICAgICAgaWYgaXNpbnN0YW5jZShnb3QsIGFzdC5DYWxsKToKICAgICAgICAgICAgaWYgbm90IGlzaW5zdGFuY2UoZ290LmZ1bmMsIGFzdC5OYW1lKToKICAgICAgICAgICAgICAgIHJldHVybgogICAgICAgICAgICBuYW1lID0gZ290LmZ1bmMuaWQKICAgICAgICAgICAgZnVuYyA9IGZyYW1lLmZfbG9jYWxzW25hbWVdCiAgICAgICAgICAgIGlmIG5vdCBoYXNhdHRyKGZ1bmMsIERFQlVHR0FCTEVfQVJHUyk6CiAgICAgICAgICAgICAgICByZXR1cm4KICAgICAgICAgICAgYXJncyA9IGdldGF0dHIoZnVuYywgREVCVUdHQUJMRV9BUkdTKQogICAgICAgICAgICBrd2FyZ3MgPSBnZXRhdHRyKGZ1bmMsIERFQlVHR0FCTEVfS1dBUkdTKQogICAgICAgICAgICBib3VuZGFyZ3MgPSBpbnNwZWN0LnNpZ25hdHVyZShmdW5jKS5iaW5kKCphcmdzLCAqKmt3YXJncykKCiAgICAgICAgICAgIHJlc3VsdCA9IGlvLlN0cmluZ0lPKCkKICAgICAgICAgICAgcG9zID0gcmVzdWx0LndyaXRlKG5hbWUpCiAgICAgICAgICAgIHBvcyArPSByZXN1bHQud3JpdGUoIigiKQoKICAgICAgICAgICAgc2VwID0gJywgJwogICAgICAgICAgICBhcmdfdHVwbGVzID0gW10gICMgKGFzdF9hcmdfc3RyLCBldmFsdWF0ZWRfYXJnLCBzdGFydCwgbGltaXQpCgogICAgICAgICAgICAjIFVzZSBhbiBpdGVyYXRvciBoZXJlLiBJZiBhIGJvdW5kYXJnIGlzIG5vdCBjb25zdW1lZCBoZXJlLAogICAgICAgICAgICAjIGl0IG1heSBiZSBjb25zdW1lZCBsYXRlciBieSBhIHBvcytrdyBhcmcuCiAgICAgICAgICAgIGJvdW5kYXJnc19pdGVyID0gaXRlcihib3VuZGFyZ3MuYXJncykKICAgICAgICAgICAgZm9yIGFzdF9hcmcsIGFyZyBpbiB6aXAoZ290LmFyZ3MsIGJvdW5kYXJnc19pdGVyKToKICAgICAgICAgICAgICAgIGFzdF9hcmdfc3RyID0gYXN0LnVucGFyc2UoYXN0X2FyZykKICAgICAgICAgICAgICAgIGFyZ190dXBsZXMuYXBwZW5kKChhc3RfYXJnX3N0ciwgYXJnLCBwb3MsIHBvcyArIGxlbihhc3RfYXJnX3N0cikpKQogICAgICAgICAgICAgICAgcG9zICs9IGxlbihhc3RfYXJnX3N0cikgKyBsZW4oc2VwKQoKICAgICAgICAgICAgZm9yIGFzdF9rd2FyZywga3dhcmcgaW4gaXRlcnRvb2xzLnppcF9sb25nZXN0KGdvdC5rZXl3b3JkcywgYm91bmRhcmdzX2l0ZXIpOgogICAgICAgICAgICAgICAgYXN0X2FyZ19zdHIgPSBhc3QudW5wYXJzZShhc3Rfa3dhcmcpCiAgICAgICAgICAgICAgICBhcmdfdHVwbGVzLmFwcGVuZCgoYXN0X2FyZ19zdHIsIGt3YXJnLCBwb3MgKyBsZW4oYXN0X2t3YXJnLmFyZykgKyBsZW4oJz0nKSwgcG9zICsgbGVuKGFzdF9hcmdfc3RyKSkpCiAgICAgICAgICAgICAgICBwb3MgKz0gbGVuKGFzdF9hcmdfc3RyKSArIGxlbihzZXApCgogICAgICAgICAgICBwb3MgLT0gbGVuKHNlcCkKICAgICAgICAgICAgcmVzdWx0LndyaXRlKHNlcC5qb2luKHRbMF0gZm9yIHQgaW4gYXJnX3R1cGxlcykpCiAgICAgICAgICAgIHJlc3VsdC53cml0ZSgnKScpCiAgICAgICAgICAgIHJlc3VsdF9zdHIgPSByZXN1bHQuZ2V0dmFsdWUoKQoKICAgICAgICAgICAgeWllbGQgcmVzdWx0X3N0cgoKICAgICAgICAgICAgbm9ubGl0ZXJhbHMgPSBbXSAgIyAoZXZhbHVhdGVkX2FyZywgcmVzdWx0X3N0ciwgc3RhcnQsIGxpbWl0KQogICAgICAgICAgICBmb3IgXywgZXZhbHVhdGVkX2FyZywgc3RhcnQsIGxpbWl0IGluIGFyZ190dXBsZXM6CiAgICAgICAgICAgICAgICBpZiBub3QgaXNfbGl0ZXJhbChyZXN1bHRfc3RyW3N0YXJ0OmxpbWl0XSk6CiAgICAgICAgICAgICAgICAgICAgbm9ubGl0ZXJhbHMuYXBwZW5kKChldmFsdWF0ZWRfYXJnLCByZXN1bHRfc3RyW3N0YXJ0OmxpbWl0XSwgc3RhcnQsIGxpbWl0KSkKCiAgICAgICAgICAgIHVuZGVybGluZXMgPSBpby5TdHJpbmdJTygpCiAgICAgICAgICAgIHBvcyA9IDAKICAgICAgICAgICAgZm9yIF8sIF8sIHN0YXJ0LCBsaW1pdCBpbiBub25saXRlcmFsczoKICAgICAgICAgICAgICAgIGlmIChsaW1pdCAtIHN0YXJ0KSA8IDM6CiAgICAgICAgICAgICAgICAgICAgcG9zICs9IHVuZGVybGluZXMud3JpdGUoJyAnICogKHN0YXJ0IC0gcG9zKSkKICAgICAgICAgICAgICAgICAgICBwb3MgKz0gdW5kZXJsaW5lcy53cml0ZSgn4oaRJykKICAgICAgICAgICAgICAgICAgICBwb3MgKz0gdW5kZXJsaW5lcy53cml0ZSgn4oaRJyAqIChsaW1pdCAtIHBvcykpCiAgICAgICAgICAgICAgICAgICAgY29udGludWUKICAgICAgICAgICAgICAgIGlkeCA9IHN0YXJ0ICsgKGxpbWl0IC0gc3RhcnQpIC8vIDIKICAgICAgICAgICAgICAgIHBvcyArPSB1bmRlcmxpbmVzLndyaXRlKCcgJyAqIChzdGFydCAtIHBvcykpCiAgICAgICAgICAgICAgICAjcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KVmScpCiAgICAgICAgICAgICAgICBwb3MgKz0gdW5kZXJsaW5lcy53cml0ZSgn4oaRJyAqIChpZHggLSBwb3MpKQogICAgICAgICAgICAgICAgcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KGkScpCiAgICAgICAgICAgICAgICBwb3MgKz0gdW5kZXJsaW5lcy53cml0ZSgn4oaRJyAqIChsaW1pdCAtIHBvcykpCiAgICAgICAgICAgICAgICAjcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KVnCcpCiAgICAgICAgICAgIHlpZWxkIHVuZGVybGluZXMuZ2V0dmFsdWUoKQoKICAgICAgICAgICAgZGVmIG1ha2VfYmFyc19idWYobm9ubGl0ZXJhbHMsIGVuZCwgZXZhbGVkKToKICAgICAgICAgICAgICAgIGJ1ZiA9IGlvLlN0cmluZ0lPKCkKICAgICAgICAgICAgICAgIHBvcyA9IDAKICAgICAgICAgICAgICAgIGZvciBpIGluIHJhbmdlKGxlbihub25saXRlcmFscykgLSAxKToKICAgICAgICAgICAgICAgICAgICBfLCBfLCBzdGFydCwgbGltaXQgPSBub25saXRlcmFsc1tpXQogICAgICAgICAgICAgICAgICAgIGlmIChsaW1pdCAtIHN0YXJ0KSA8IDM6CiAgICAgICAgICAgICAgICAgICAgICAgIGlkeCA9IHN0YXJ0CiAgICAgICAgICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgICAgICAgICAgaWR4ID0gc3RhcnQgKyAobGltaXQgLSBzdGFydCkgLy8gMgogICAgICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUoJyAnICogKGlkeCAtIHBvcykpCiAgICAgICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZSgn4pSCJykKICAgICAgICAgICAgICAgICAgICBwb3MgKz0gYnVmLndyaXRlKCcgJyAqIChsaW1pdCAtIHBvcykpCgogICAgICAgICAgICAgICAgXywgcmVzdWx0X3N0ciwgc3RhcnQsIGxpbWl0ID0gbm9ubGl0ZXJhbHNbLTFdCiAgICAgICAgICAgICAgICBpZiAobGltaXQgLSBzdGFydCkgPCAzOgogICAgICAgICAgICAgICAgICAgIGlkeCA9IHN0YXJ0CiAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgIGlkeCA9IHN0YXJ0ICsgKGxpbWl0IC0gc3RhcnQpIC8vIDIgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICBwb3MgKz0gYnVmLndyaXRlKCcgJyAqIChpZHggLSBwb3MpKQogICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZSgn4pSUJykKICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUoJ+KUgCcgKiAoZW5kIC0gMSAtIHBvcykpCiAgICAgICAgICAgICAgICBwb3MgKz0gYnVmLndyaXRlKCfilbQnKQogICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZShyZXN1bHRfc3RyKQogICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZSgnIOKJlCAnKQogICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZShzdHIoZXZhbGVkKSkKCiAgICAgICAgICAgICAgICByZXR1cm4gYnVmLCBwb3MKCiAgICAgICAgICAgIHdoaWxlIG5vbmxpdGVyYWxzOgogICAgICAgICAgICAgICAgYnVmLCBwb3MgPSBtYWtlX2JhcnNfYnVmKG5vbmxpdGVyYWxzLCBsZW4ocmVzdWx0X3N0cikgKyA0LCBub25saXRlcmFsc1stMV1bMF0pCiAgICAgICAgICAgICAgICB5aWVsZCBidWYuZ2V0dmFsdWUoKQogICAgICAgICAgICAgICAgbGFzdCA9IG5vbmxpdGVyYWxzLnBvcCgpCgogICAgZGVmIGFzc2VydF9lcXVhbCgqLCB3YW50LCBnb3QsIG91dD1zeXMuc3Rkb3V0KToKICAgICAgICBpZiB3YW50ID09IGdvdDoKICAgICAgICAgICAgcHJpbnQoIlRlc3QgY2FzZSBwYXNzZWQuIikKICAgICAgICAgICAgcmV0dXJuCgogICAgICAgIGZyYW1lID0gaW5zcGVjdC5jdXJyZW50ZnJhbWUoKS5mX2JhY2sKCiAgICAgICAgYm94X3BhZGRpbmcgPSAyCiAgICAgICAgaGVhZGVyID0gIiBUZXN0IGNhc2UgZmFpbGVkLiAiCiAgICAgICAgd2FudF9saW5lID0gZiJ7Ym94X3BhZGRpbmcgKiAnICd9V2FudDoge3JlcHIod2FudCl9ICh0eXBlOiB7dHlwZSh3YW50KS5fX25hbWVfX30pIgogICAgICAgIGdvdF9saW5lID0gZiJ7Ym94X3BhZGRpbmcgKiAnICd9R290OiAge3JlcHIoZ290KX0gKHR5cGU6IHt0eXBlKGdvdCkuX19uYW1lX199KSIKICAgICAgICAKICAgICAgICBpZiBjYW5fYW5ub3RhdGUoZnJhbWUpOgogICAgICAgICAgICBhc3NlcnRfbGluZSA9IGYie2JveF9wYWRkaW5nICogJyAnfT4+PiB7YXN0LnVucGFyc2UoZ2V0X2Fzc2VydF9saW5lKGZyYW1lKSl9IgogICAgICAgIGVsc2U6CiAgICAgICAgICAgIGFzc2VydF9saW5lID0gIiIKICAgICAgICAgICAgCiAgICAgICAgZGVidWdfbGluZXMgPSBsaXN0KGFubm90YXRlX2NhbGwoZnJhbWUpKQogICAgICAgIGlmIGRlYnVnX2xpbmVzOgogICAgICAgICAgICBnb3RfbGluZSArPSAiIOKGkCAiCiAgICAgICAgICAgIHBhZGRpbmcgPSBsZW4oZ290X2xpbmUpCiAgICAgICAgICAgIGdvdF9saW5lICs9IGRlYnVnX2xpbmVzWzBdCgogICAgICAgIHBhZGRlZF9kZWJ1Z19saW5lcyA9IFtdCiAgICAgICAgZm9yIGksIGxpbmUgaW4gZW51bWVyYXRlKGRlYnVnX2xpbmVzKToKICAgICAgICAgICAgICAgIGlmIGkgPT0gMDoKICAgICAgICAgICAgICAgICAgICBjb250aW51ZQogICAgICAgICAgICAgICAgcGFkZGVkX2RlYnVnX2xpbmVzLmFwcGVuZCgnICcgKiBwYWRkaW5nICsgbGluZSkKICAgICAgICAgICAgICAgIAogICAgICAgIGxpbmVfbWF4X2xlbiA9IG1heChsZW4obCkgKyBib3hfcGFkZGluZyBmb3IgbCBpbiAoYXNzZXJ0X2xpbmUsIHdhbnRfbGluZSwgZ290X2xpbmUsICpwYWRkZWRfZGVidWdfbGluZXMpKQogICAgICAgIGxpbmVfbWF4X2xlbiA9IG1heCgzMiwgbGluZV9tYXhfbGVuKQogICAgICAgIGhlYWRlcl9kYXNoZXMgPSBsaW5lX21heF9sZW4gLSBsZW4oaGVhZGVyKQoKCiAgICAgICAgcHJpbnQoZmlsZT1vdXQpCiAgICAgICAgcHJpbnQoJy0nICogKGhlYWRlcl9kYXNoZXMgLy8gMiksIGVuZD0iIiwgZmlsZT1vdXQpCiAgICAgICAgcHJpbnQoaGVhZGVyLCBlbmQ9IiIsIGZpbGU9b3V0KQogICAgICAgIHByaW50KCctJyAqICgoaGVhZGVyX2Rhc2hlcyArIDEpIC8vIDIpLCBlbmQ9IiIsIGZpbGU9b3V0KQogICAgICAgIHByaW50KGZpbGU9b3V0KQogICAgICAgIHByaW50KGZpbGU9b3V0KQoKICAgICAgICAKICAgICAgICBpZiBhc3NlcnRfbGluZToKICAgICAgICAgICAgcHJpbnQoYXNzZXJ0X2xpbmUsIGZpbGU9b3V0KQogICAgICAgICAgICBwcmludChmaWxlPW91dCkKCiAgICAgICAgcHJpbnQod2FudF9saW5lLCBmaWxlPW91dCkKICAgICAgICBwcmludChnb3RfbGluZSwgZmlsZT1vdXQpCiAgICAgICAgZm9yIGxpbmUgaW4gcGFkZGVkX2RlYnVnX2xpbmVzOgogICAgICAgICAgICBwcmludChsaW5lLCBmaWxlPW91dCkKICAgICAgICAKICAgICAgICBwcmludChmaWxlPW91dCkKICAgICAgICBwcmludCgnLScgKiBsaW5lX21heF9sZW4sIGZpbGU9b3V0KQogICAgICAgIHByaW50KGZpbGU9b3V0KQogICAgICAgIAogICAgREVCVUdHQUJMRV9BUkdTID0gIl9kZWJ1Z2dhYmxlX2FyZ3MiCiAgICBERUJVR0dBQkxFX0tXQVJHUyA9ICJfZGVidWdnYWJsZV9rd2FyZ3MiCgogICAgZGVmIGRlYnVnZ2FibGUoZik6CiAgICAgICAgaW1wb3J0IGZ1bmN0b29scwogICAgICAgIEBmdW5jdG9vbHMud3JhcHMoZikKICAgICAgICBkZWYgZygqYXJncywgKiprd2FyZ3MpOgogICAgICAgICAgICByZXN1bHQgPSBmKCphcmdzLCAqKmt3YXJncykKICAgICAgICAgICAgc2V0YXR0cihnLCBERUJVR0dBQkxFX0FSR1MsIGFyZ3MpCiAgICAgICAgICAgIHNldGF0dHIoZywgREVCVUdHQUJMRV9LV0FSR1MsIGt3YXJncykKICAgICAgICAgICAgcmV0dXJuIHJlc3VsdAogICAgICAgIHJldHVybiBnCiAgICAKICAgIHJldHVybiBhc3NlcnRfZXF1YWwsIGRlYnVnZ2FibGUKCmFzc2VydF9lcXVhbCwgZGVidWdnYWJsZSA9IG1ha2VfcHJldHR5X2Fzc2VydCgpCg==")
for code in CODE:
exec(base64.b64decode(code), globals, locals)
f(globals(), locals())
del f
def uh(b64):
return eval(base64.b64decode(b64))
def h(code):
return base64.b64encode(code)
def sae(*, want, got):
assert_equal(want=sorted(want), got=sorted(got))
```

**Classes** provide a means of bundling data and functionality together. Creating a new class creates a new type of object, allowing new instances of that type to be made. Each class instance can have attributes attached to it for maintaining its state. Class instances can also have methods (defined by its class) for modifying its state. [The Python Tutorial, Chapter 9]

In this lab, we'll think about three important components of a class:

**Attributes**: data that an instance of a class "remembers" about its state.**Methods**: functions associated with a class that may change its attributes.**Initializer**: a special method that creates a new instance of a class.

Let's take a look at a simple class that represents a student.

In [ ]:

```
class Student:
"""Represents a high school student (name, age and school).
"""
def __init__(self, name, school, form):
"""Creates a representation of a student.
Arguments: name (str), form (int, between 1 and 6), school (str).
Effects: Initializes the Student instance.
"""
self.name = name
self.school = school
self.form = form
self.graduated = False
def next_year(self):
"""Advances the student to the next school year.
Effects: Updates the student's form or graduated attribute.
"""
if self.form == 6:
self.graduated = True
else:
self.form += 1
def can_attend_jamcoders(self):
"""Checks whether the student can attend JamCoders.
Returns: (bool).
Effects: No effects.
"""
return self.form <= 5 and self.form >= 3
```

Let's look at the components of the above code piece by piece (we'll skip docstrings).

```
class Student:
```

The `class`

keyword tells Python we are declaring a class, and `Student`

is the name of the class. The three functions defined in this scope are methods of `Student`

.

```
def __init__(self, name, school, form):
self.name = name
self.school = school
self.form = form
self.graduated = False
```

The initalizer method of the `Student`

class. In Python, the initializer is named `__init__`

(we'll see how to call it in a bit). The initializer takes in values of three of the attributes: `name`

, `school`

and `form`

. The attribute `graduated`

is always initialized to be `False`

.

```
def next_year(self):
if self.form == 6:
self.graduated = True
else:
self.form += 1
def can_attend_jamcoders(self):
return self.form <= 5 and self.form >= 3
```

Two more methods of the `Student`

class. The nice thing about classes is that they bundle together data and how to interact with it. In this case, the `next_year`

method handles the logic behind checking whether a student has graduated. Similarly, `can_attend_jamcoders`

keeps the logic of the JamCoders student requirements (between third and fifth form) neatly with the relevant data (`form`

).

Here's how we use classes in Python:

In [ ]:

```
alani = Student("Alani", "Immaculate", 5) # Calls the __init__ function
print(alani.name) # Access attributes using a dot .
print(alani.school)
print(alani.form)
print(alani.can_attend_jamcoders()) # Similarly, call methods using a dot .
```

Soon the summer will be over, and Alani will be in sixth form. Could Alani attend JamCoders next year as well?

In [ ]:

```
alani.next_year()
print(alani.can_attend_jamcoders())
```

Next, we'll load a mystery student. Can you find out their identity using attributes and methods?

In [ ]:

```
mystery_student = uh(b'U3R1ZGVudCgiQ2xheXRvbiIsICJHbGVubXVpciIsIDUp') # Weird code that loads the mystery student
```

In [ ]:

```
# Your code here
```

Last week (`probs13a`

) we introduced the Stack data structure. We then implemented the following interface:

`init_s()`

: Constructs a new empty Stack.`push_s(stack, elem)`

: Adds an element,`elem`

, to the top of the Stack`stack`

.`pop_s(stack)`

: Removes the frontmost/popmost element in the Stack`stack`

and returns its value.`top_s(stack)`

: Returns the value of the frontmost/ element in the Stack`stack`

without removing it.`is_empty_s(stack)`

: Tests whether or not Stack`stack`

is empty.

It's natural to think of a Stack as a Class; then, the above interface will instead be implemented as methods of this class---rather than a collection of functions that happen to end with `_s`

.

`Stack`

class¶Next, we'll implement a stack (again), this time as a class called `Stack`

. Feel free to adapt your solution to question 2.2 in `probs13a`

.

In [ ]:

```
class Stack:
"""An implementation of the stack data structure.
"""
@debuggable
def __init__(self, lst=[]):
"""Constructs a new Stack, optionally initialized with the elements of lst.
Arguments: lst (Optional[list])
Effects: Initializes the Stack.
"""
if lst is None:
self.data = []
else:
self.data = lst[:]
@debuggable
def push(self, elem):
"""Adds an element to the top of the stack
Arguments:
elem (any): The element to be pushed onto the stack.
Effects: Adds the element on top of the stack.
"""
# YOUR CODE HERE
@debuggable
def pop(self):
"""Remove the element on top of the stack.
Returns (any): The element on the top of the stack
Effects: Removes the top element from the stack.
"""
return self.data.pop()
@debuggable
def top(self):
"""Returns the value of the topmost element on the stack without removing it.
Returns (any): The element on the top of stack.
"""
return self.data[-1]
@debuggable
def is_empty(self):
"""Checks if the stack is empty.
Returns (bool): True if the stack is empty or False if it is not
"""
return self.data == []
```

In [ ]:

```
# Test stacks with integers.
stack = Stack()
assert_equal(want=None, got=stack.push(1)) # Stack contains [1]
assert_equal(want=None, got=stack.push(3)) # Stack contains [1, 3]
assert_equal(want=None, got=stack.push(2)) # Stack contains [1, 3, 2]
assert_equal(want=None, got=stack.push(5)) # Stack contains [1, 3, 2, 5]
assert_equal(want=5, got=stack.pop())
assert_equal(want=2, got=stack.pop()) # Stack contains [1, 3, 2, 5]
assert_equal(want=3, got=stack.top())
assert_equal(want=False, got=stack.is_empty())
# Test stack with other types.
stack = Stack()
stack.push("Hello")
stack.push("Goodbye")
stack.push([])
# Stacks pop in last-in-first-out.
assert_equal(want=[], got=stack.pop())
assert_equal(want="Goodbye", got=stack.pop())
assert_equal(want="Hello", got=stack.pop())
# Test empty stacks.
stack = Stack()
assert_equal(want=True, got=stack.is_empty())
```

Let's take a moment to look the differences between the old implementation and the new one. The following table compares code for initializing and manipulating a stack `stck`

in both implementations.

Operation | `Stack` class |
`probs13b` implementation |
---|---|---|

Initialize `stck` |
`stck = Stack()` |
`stck = init_s()` |

Push `elem` |
`stck.push(elem)` |
`push_s(stck, elem)` |

Pop | `stck.pop()` |
`pop_s(stck)` |

Peek | `stck.peek()` |
`peek_s(stck)` |

Check if empty | `stck.is_empty()` |
`is_empty_s(stck)` |

Which syntax do you like better? Why?

In [ ]:

```
# Your thoughts here
```

Alright, so we dropped the `_s`

's and use `.`

's instead. But is there any other difference other than the way we write our programs?

Yes! If we use classes, Python can protect us from sneaky bugs. Look back at the interface of Stack. Notice that it does **not** support arbitrary access to elements: unlike Lists, you should not be able to use `stack[i]`

to access the i-th element of a stack---the whole point of using a Stack is that you can only access the topmost element!

Recall our old implementation of Stack, from `probs13b`

In [ ]:

```
def init_s(lst=[]):
"""Old code for implementing a stack, from probs13b.
"""
if lst is None:
return []
return lst[:]
def push_s(stack, elem):
stack.append(elem)
def top_s(stack):
return stack[-1]
```

We now have a stack of three dirty plates. Without popping the top plate (Bereket's), we should not be able to access any of the other plate. Imagine grabbing a plate from the middle of a stack of dirty dishes---the whole thing would come tumbling down!

In [ ]:

```
print(f"Plate on top is: {top_s(dishes)}") # Prints Top; ok.
print(f"Grabbing {dishes[1]}") # Oops! We aren't supposed to do this!
print("Boom, crash, clang!")
```

Uh oh! The problem was that we accessed `dishes[1]`

; `dishes`

is a Stack, but Python allowed us to access the underlying list and grab Tyler's Bowl from the middle... If we use the `Stack`

class, this issue cannot happen. Take a look:

In [ ]:

```
dishes = Stack()
dishes.push("Orr's Cup")
dishes.push("Tyler's Bowl")
dishes.push("Berket's Bowl")
print(f"Plate on top is: {dishes.top()}") # Prints Top; ok.
print(f"Grabbing plate {dishes[1]}") # Oops! We aren't supposed to do this!
print("Boom, crash, clang!")
```

Take a look at the last line above. See that `TypeError`

? `'Stack' is not subscriptable`

is Python's way of telling us that you cannot access any element you want from a Stack. Thanks, Python!

More generally, this concept is called **encapsulation**. From Wikipedia:

Encapsulation is used to hide the values or state of a structured data object inside a class, preventing direct access to them by clients in a way that could expose hidden implementation details or violate state invariance maintained by the methods.

By hiding our implementation details (the fact that our Stack is based on an underlying List), we prevented users from violating an important invariance of the Stack (that only the top object may be accessed).

Remember last week's Graphs lab (`jamcoders_14a`

)? Ever wondered how graphs were *really* stored on the computer? In this question we'll offer one possible answer by implementing our very own `Graph`

class!

An **undirected graph** is a mathematical object that consists of **nodes** and **edges**. Each edge represents a connection between two nodes.

- This is a graph with three vertices and three edges:

- And this is a graph with 102 vertices and 153 edges:

There are many ways to implement graphs in a computer, each with its own advantages and disadvantages. We'll base our implementation on a `dict`

because it's simple (and relatively fast).

This is the plan:

- The Graph class is initialized with an empty
`dict`

attribute called`self.data`

. - The keys of
`self.data`

are strings that represent nodes in the graph. The value of each key is the adjacency list of the node.- For example, having
`self.data == {'a': ['b', 'c'], 'b': ['a', 'c'], 'c': ['a', 'b']}`

means that our graph has three nodes, where each node is connected to all other nodes -- a triangle (like in the reminder).

- For example, having
- Nodes are added by calling
`graph.add_node(node_label)`

method. Each node has a string label. When a node is just added, its adjacency list is empty. - Edges are added with the
`graph.add_edge(node1, node2)`

method.- You may assume that the nodes are different (no loops).
- Since we are implementing
*undirected*graphs, you will need to update the adjacency list of`node1`

*and*`node2`

.

- The
`graph.get_nodes()`

method returns a list of all nodes in the graph. We've implemented this method for you. - The
`graph.get_neighbors(node)`

method returns a list of nodes neighboring`node`

(i.e., that share an edge with`node`

). - A
`draw`

method. We've implemented this method for you.

Alright, let's do this. Replace the `# YOUR CODE HERE`

's in the next cell with, umm, your code.

In [ ]:

```
`class Graph:
"""Represents a mathematical graph consisting of nodes and edges.
"""
def __init__(self):
"""Initializes an empty graph.
"""
# Initialize self.data with an empty dict
# Eventually, this dict will map {node: [list of neighbors]}.
self.data = # YOUR CODE HERE
def add_node(self, node_label):
"""Adds a node to the graph.
The node is associated with a string node_label which is used to add edges to it later.
If a node associated with node_label already exists, does nothing.
Arguments: node_label (string).
Returns: (None).
Effects: Modifies the graph. If the node already exists, does nothing.
"""
# First, check if a node associated with node_label already exists
# Hint: The expression "k in dict" is True if dict has a key called 'k' (else False).
# If the node doesn't already exist, add it by initializing an empty adjacency list []
self.data[node_label] = # YOUR CODE HERE
def add_edge(self, node1, node2):
"""Connects node1 and node2 with an edge.
Arguments: node1 (string), node2 (string).
Returns: (None).
Effects: Modifies the graph. If an edge already exists, does nothing.
"""
# First, check if the nodes are already connected
# Hint: The expression "x in list" is True if list contains the element 'x' (else False).
# If they aren't already connected, connect them by adding each to the other's adjacency list.
self.data[node1] += # YOUR CODE HERE
self.data[node2] += # YOUR CODE HERE
def get_nodes(self):
"""Returns a list of all nodes in the graph. (Already implemented by TAs)
Returns: (list of strings).
Effects: None.
"""
return list(self.data.keys()) # Need to cast to list because .keys() returns a dict_keys object...
def get_neighbors(self, node):
"""Returns list of neighbors of node.
Arguments: node (string).
Returns: (list of string).
Effects: None.
"""
# YOUR CODE HERE
def draw(self):
"""Draws graph. (Already implemented by TAs)
Effects: Prints drawing of graph.
"""
# Create set of edges
edges = set(tuple(sorted([u, v])) for u, neighbs in self.data.items() for v in neighbs)
# Create nx graph
nx_graph = nx.Graph()
nx_graph.add_edges_from(edges)
# Draw
nx.draw(nx_graph, with_labels=True)
```

In [ ]:

```
Now let's test your code.
```

In [ ]:

```
# Test your code by running this cell.
# Test graph init, adding two nodes and connecting them.
graph = Graph()
assert_equal(want=None, got=graph.add_node("a"))
assert_equal(want=[], got=graph.get_neighbors("a"))
assert_equal(want=["a"], got=graph.get_nodes())
assert_equal(want=None, got=graph.add_node("b"))
sae(want=["a", "b"], got=graph.get_nodes()) # Sort because order doesn't matter.
assert_equal(want=[], got=graph.get_neighbors("a"))
assert_equal(want=[], got=graph.get_neighbors("b"))
assert_equal(want=None, got=graph.add_edge("a", "b"))
assert_equal(want=["b"], got=graph.get_neighbors("a"))
assert_equal(want=["a"], got=graph.get_neighbors("b"))
# Test adding an existing node
assert_equal(want=None, got=graph.add_node("a"))
sae(want=["a", "b"], got=graph.get_nodes())
# Test adding an existing edge
assert_equal(want=None, got=graph.add_edge("a", "b"))
assert_equal(want=None, got=graph.add_edge("b", "a")) # Reverse order, shouldn't matter.
assert_equal(want=["b"], got=graph.get_neighbors("a"))
assert_equal(want=["a"], got=graph.get_neighbors("b"))
# Test adding a new node "c" and connect it to "b"
assert_equal(want=None, got=graph.add_node("c"))
sae(want=["a", "b", "c"], got=graph.get_nodes())
assert_equal(want=None, got=graph.add_edge("c", "b"))
sae(want=["a", "c"], got=graph.get_neighbors("b"))
sae(want=["b"], got=graph.get_neighbors("c"))
# Now connect "c" to "a" to form a triangle
assert_equal(want=None, got=graph.add_edge("c", "a"))
sae(want=["b", "c"], got=graph.get_neighbors("a"))
sae(want=["a", "b"], got=graph.get_neighbors("c"))
graph.draw() # Should look like a triangle
```

Sometimes we want to remove edges from a graph. In this challenge you will enrich your `Graph`

class with this functioanlity.

In [ ]:

```
class Graph2(Graph):
def remove_edge(self, node1, node2):
"""Removes an edge between node1 and node2 if it exists. If it doesn't, does nothing.
Arguments: node1 (string), node2 (string).
Effects: Modifies the graph. If no edge was present, does nothing.
"""
# Hint: list.remove(elem) removes elem from list -- if it exists.
# list.remove(elem) will error if elem is not in list. So check that first.
# YOUR CODE HERE
def remove_node(self, node):
"""Removes node and all edges touching it. If node is not in graph, does nothing.
Arguments: node (string).
Effects: Modifies the graph. If node was not in the graph, does nothing.
"""
# Hint #1: See previous hint...
if node not in self.get_nodes():
return
neighbors_copy = self.get_neighbors(node)[:]
# Ponder: why must we make a copy of the neighbors list above?
for neighbor in neghighbors_copy:
# YOUR CODE HERE
# Finally, delete the node entry from self.data
# Hint #2: 'del dict[k]' deletes key 'k' from dict.
# YOUR CODE HERE
```

Next you can test your code. You may uncomment the `graph.draw()`

statements one-at-a-time to see the graph change (be sure to uncomment them only one at a time, else all the drawings will render on top of each other...)

In [ ]:

```
# Now test your code
from itertools import permutations
# Create a 4-clique (square with both diagonals).
graph = Graph2()
# We'll access data manually to avoid writing 4 + (4 choose 2) = 10 lines of code
graph.data = {x: [y, z, w] for x, y, z, w in permutations(['a', 'b', 'c', 'd'])}
# graph.draw()
# Then remove the edge between 'a' and 'b'
assert_equal(want=None, got=graph.remove_edge('a', 'b'))
sae(want=['c', 'd'], got=graph.get_neighbors('a'))
sae(want=['c', 'd'], got=graph.get_neighbors('b'))
sae(want=['a', 'b', 'd'], got=graph.get_neighbors('c'))
sae(want=['a', 'b', 'c'], got=graph.get_neighbors('d'))
# graph.draw()
# Then remove the node 'c'
assert_equal(want=None, got=graph.remove_node('c'))
sae(want=['d'], got=graph.get_neighbors('a'))
sae(want=['d'], got=graph.get_neighbors('b'))
sae(want=['a', 'b'], got=graph.get_neighbors('d'))
# graph.draw()
```

Design and implement the `Queue`

class, which supports the following operations:

**Initialize**: Constructs a new empty queue.**Enqueue**: Adds an element to the back of the queue.**Peek**: Returns the value of the frontmost element in the queue, without removing it.**Deqeueue**: Removes the frontmost element in the queue and returns its value.**Is empty?**: Returns whether or not queue is empty.

You may want to refer to your solution of Question 1 in this notebook, and Question 1 in `probs13a`

. The challenging aspect of this question is in writing a bunch of code on your own, without guidance and ready-made tests.

In [ ]:

```
class Queue:
"""An implementation of the queue data structure
"""
# YOUR CODE HERE
```