06.rs

use std::time::Instant;
use std::collections::{HashMap, HashSet};

const INPUT: [(&str,&str); 1621] = [("WX9","CQ4"),("7LX","WVR"),("25Q","7HB"),("DCB","979"),("KY3","Q2M"),("CBN","88V"),("T81","99L"),("QB8","8KY"),("BK3","58Y"),("3SC","9JM"),("4S2","3G5"),("GWZ","7BM"),("QS4","CVW"),("SVC","LFW"),("5PV","N8K"),("LN3","96T"),("WCC","VM1"),("BP1","Z48"),("NSY","SKN"),("27N","GS6"),("VMB","TZG"),("T92","ZN9"),("PCB","NZJ"),("WLM","967"),("WM7","GHX"),("BM6","VTC"),("F8M","QVJ"),("NPT","8DL"),("2RN","D4V"),("CNB","LZ6"),("8KY","T1F"),("RZJ","6WS"),("ZLS","YGK"),("D8G","MST"),("J3T","R19"),("WD1","WC6"),("2Y6","TYP"),("169","C38"),("742","Z2D"),("TQM","7KJ"),("R5T","DJC"),("9L6","LFD"),("ZL5","RW8"),("ZYY","VN5"),("4NT","W65"),("2B7","NRQ"),("HM1","4QJ"),("G7Q","4M2"),("NZJ","LTV"),("JZN","FJS"),("49Q","K49"),("VN9","M1S"),("DTZ","5PX"),("1JB","8CJ"),("W2X","BGL"),("3X5","ZZH"),("1MW","6L2"),("JKG","P1V"),("M65","NYX"),("PWW","GFR"),("YVF","MZ5"),("PZY","8KZ"),("L6T","R3D"),("1ZG","1MB"),("3X6","17C"),("ZQK","N6T"),("JH4","T92"),("FYM","M7Q"),("D7F","33M"),("SDX","DTZ"),("2LN","N41"),("XTN","NFY"),("MX5","N6B"),("WDH","75Q"),("8YX","XPH"),("9XN","H34"),("CH3","1M2"),("HMN","W75"),("Q3Q","ZP4"),("GDM","Y3S"),("TD1","45C"),("XBP","K2Y"),("Y5P","XHL"),("Y6G","Z7R"),("JDM","TGB"),("GH2","P7T"),("CD4","85Z"),("782","M16"),("BCD","2ZC"),("ZZH","1H4"),("7CW","62C"),("KRV","TQM"),("SMD","FHS"),("NJ6","4SZ"),("WCQ","4V2"),("QBK","R3B"),("YQR","ZJD"),("8LQ","95J"),("FB7","SDP"),("H34","1PD"),("YMY","K4K"),("F95","K2K"),("99H","B32"),("9CZ","N6Y"),("QGG","TJ9"),("TK3","95Y"),("6C8","3YZ"),("ZJ8","DK4"),("7W5","8ZX"),("DQ1","BRG"),("6L2","NYY"),("1MB","G95"),("ZFH","LFC"),("1KD","1KQ"),("F69","VZM"),("X4C","L3F"),("BJ4","DQ1"),("6GT","FTL"),("DY5","K82"),("LJN","L45"),("TXN","BMP"),("LN3","3BH"),("FFC","87T"),("P7T","6PJ"),("DDT","ZHL"),("2QM","39Y"),("7RB","VSC"),("7QQ","YD8"),("M37","JT6"),("36C","729"),("86S","VBH"),("C38","7H3"),("3Z4","N31"),("V94","BW5"),("HLN","6JD"),("LTZ","D6T"),("DJC","C2K"),("XT7","HHF"),("WQD","T46"),("J25","QS4"),("4FR","5PV"),("L62","X36"),("1N3","RD8"),("GPR","27J"),("CBZ","DB6"),("RZ2","99R"),("B9P","FCY"),("TSS","T9Z"),("Y5X","RP7"),("GMW","MMJ"),("G7W","4M8"),("1F3","XH9"),("K1S","VGS"),("M75","JH4"),("SBG","XBP"),("GX2","R5T"),("JQ8","CZY"),("VBH","B93"),("3Z4","37X"),("LFD","5LF"),("PRX","RN8"),("SLF","LRH"),("HLG","GH2"),("BZK","JT4"),("M64","KWF"),("5S6","JCX"),("CHW","6B3"),("DCR","7G1"),("4VP","34K"),("PJT","QQY"),("D9H","MX5"),("G2M","RJK"),("FCQ","M36"),("9YM","6SS"),("WN4","WNH"),("ZM9","FNP"),("MYG","Y91"),("XPG","X77"),("V5R","J1G"),("892","7T6"),("6RH","TL3"),("N7Z","4Y4"),("M36","L35"),("YCN","TCD"),("HN9","K3X"),("WX3","4HG"),("Z5S","CH3"),("GV5","XFB"),("P4C","CBZ"),("YL6","J28"),("7MQ","7DY"),("HZB","YLC"),("R7X","SG3"),("SWT","JLQ"),("GQM","MTQ"),("9FY","YQR"),("5M9","JP1"),("C9N","B87"),("Y22","C87"),("G56","B5P"),("5QR","N58"),("6PP","ZZV"),("ZHL","L16"),("N4N","T4Y"),("TBG","LYF"),("M33","9D5"),("8PP","NVK"),("G1W","9NX"),("4XJ","4MT"),("K1S","6RW"),("XN5","SV9"),("XH9","JXX"),("6TS","4S2"),("88C","1VD"),("H6H","7VG"),("DLS","7F3"),("VB7","7NK"),("RT8","HHG"),("51T","6ZR"),("LYG","WLM"),("65G","WF1"),("L9L","CW5"),("YZ2","2HF"),("N6B","CSK"),("Q54","6C8"),("9SN","RLY"),("7D9","8X3"),("9HZ","KWM"),("4HJ","GNK"),("D5C","4VP"),("GHY","QGY"),("BP2","MND"),("2NR","YSY"),("S27","HXY"),("XTW","1N9"),("76Z","MN6"),("6ZR","HM1"),("3MC","XCF"),("6GN","G56"),("S45","YQ1"),("RBF","VQ7"),("XVL","FYB"),("8DX","L7N"),("QN6","5M5"),("HWT","J3N"),("CVV","6L3"),("BSF","HZH"),("24F","296"),("CDQ","Q34"),("T18","BVX"),("PSC","854"),("LC3","6KT"),("GL9","SMD"),("9M6","J25"),("HN6","8ZC"),("QDN","8R1"),("WCB","RVH"),("7DY","V46"),("GJ4","955"),("GD9","L43"),("5BD","2TX"),("XHL","B9K"),("GHX","JCF"),("BP2","DFM"),("Q22","6Y1"),("9NX","YKN"),("WL9","73B"),("1TX","6Z2"),("GQB","6DG"),("H28","TF8"),("5J8","GZ2"),("VZZ","G17"),("L7F","MVB"),("JB5","QVS"),("VFY","H68"),("3Y4","XP3"),("4MT","P2W"),("4N5","PRQ"),("ZDW","9YS"),("D4V","KQ1"),("H51","5V7"),("DBH","R1X"),("T9Z","RF6"),("17C","4PN"),("LFW","C2Y"),("6YL","25Y"),("VNN","4LT"),("TBJ","8X4"),("R5Q","76Z"),("967","FWP"),("83C","GBV"),("QLM","CKT"),("KQN","G8S"),("SDP","JVH"),("ZN3","YCN"),("MST","SXH"),("5ZG","NN8"),("QGT","Y2D"),("X3X","T27"),("LHJ","DDT"),("2XH","73M"),("6YH","GLT"),("Y3R","HN9"),("F35","9YJ"),("JP1","CNL"),("6T9","VXS"),("SBL","GDM"),("LQ8","DLH"),("4CD","9MT"),("DG3","734"),("BPW","S8S"),("HD5","G7N"),("G69","H2P"),("1DF","3Y4"),("18Y","K93"),("XMN","1J4"),("Y61","XDS"),("H3B","RBF"),("QBW","3X6"),("J3N","87R"),("F5X","53Z"),("D8X","11V"),("DPS","CSX"),("SJB","LKN"),("J2R","78S"),("P2W","WCB"),("45C","1HF"),("YX3","1NN"),("MXY","B2V"),("SH7","J2R"),("6T4","VCV"),("5S6","Q5H"),("DGR","3VK"),("1XY","CMR"),("R88","VD6"),("ZFR","TYR"),("562","J4J"),("XP3","HLN"),("VLQ","8QB"),("RK9","GD9"),("HHG","XWD"),("RLD","G69"),("B7S","P68"),("8CY","FBT"),("QGQ","H6H"),("6WS","7YL"),("L7T","BPP"),("53Q","LTX"),("VHQ","Y4T"),("TGZ","MYG"),("J48","SVN"),("MGB","SPY"),("FLS","C1R"),("J28","NWT"),("M3D","13F"),("YD8","575"),("QVJ","4CD"),("SV9","T7R"),("LX6","9CZ"),("TSW","RF4"),("TQ3","Q22"),("X6X","PVQ"),("BLF","D8G"),("511","SRG"),("GQT","14T"),("3K3","TC6"),("Q7S","SH7"),("99R","RT8"),("JLF","KMW"),("NWG","QC2"),("GX2","HX6"),("VXS","DW6"),("WKZ","96Z"),("RDN","WSY"),("FK9","1ZG"),("X7Y","181"),("V17","Q79"),("X1F","BFT"),("TX7","NJ6"),("Y9S","L3M"),("95J","9X4"),("GXS","LGN"),("YMC","SVB"),("61J","GC2"),("H6Y","Q7Z"),("HRV","66N"),("V6P","TQF"),("3VK","7LX"),("JCB","H7H"),("9FY","54W"),("XT7","Y2K"),("3GN","1RD"),("TZX","21L"),("YX3","R7X"),("B87","39W"),("T2G","Q8F"),("G4T","HGR"),("R3B","6B6"),("5XR","BJ4"),("VTL","KRX"),("3Z2","8QR"),("YCS","S8W"),("8R4","6HL"),("FNM","TWM"),("7BL","2Y6"),("SY5","B6Z"),("3KW","S6F"),("4Y1","1PP"),("B7L","HD5"),("4RB","DCB"),("7NS","RTP"),("7M1","4ZZ"),("G9F","PSC"),("MTQ","TYL"),("H9V","17L"),("2Y1","WXN"),("W77","TK2"),("18D","7MQ"),("ZC5","P2Q"),("6FK","7C3"),("5YV","H9D"),("2BD","BP2"),("S89","VJY"),("V94","3MD"),("RQP","SBL"),("6CR","P27"),("R2P","7J1"),("97J","7CW"),("MD4","PHZ"),("QJ8","ZQK"),("QKR","83P"),("VRC","2CC"),("61Q","BPM"),("K5Q","RV5"),("VJY","S27"),("TZW","PWH"),("CD4","M27"),("48H","HKN"),("N7Z","PWW"),("559","844"),("H7W","FLS"),("FYB","QMS"),("HGR","Y3R"),("DKS","41X"),("XFB","WX3"),("X36","VNP"),("G17","ZDT"),("Z2B","BRS"),("YH7","7K5"),("4HG","T18"),("1KQ","S6M"),("K3X","KVQ"),("97P","386"),("SXH","14S"),("3X5","B7S"),("PHZ","CDQ"),("QYL","PST"),("Q61","G6N"),("75Z","LWF"),("W89","D95"),("79W","1WG"),("FGW","WWT"),("6NF","ZN3"),("TYR","4KJ"),("LD7","PSN"),("VLH","D5C"),("K9W","L7M"),("NN7","XTY"),("KYD","QBW"),("KJ4","XVL"),("98V","V2T"),("KHG","Z4C"),("5V9","XNH"),("XJR","BCD"),("TK2","9PP"),("C4F","1N3"),("6B6","XRJ"),("79W","GWK"),("T67","6K7"),("1RD","TLJ"),("R6H","9FJ"),("QS4","G9F"),("ZSF","D7F"),("9D5","MQT"),("L3M","Z1Q"),("TCD","V6K"),("GHN","WHD"),("NRZ","8LQ"),("9X4","V8Z"),("L16","82K"),("7NF","XD4"),("8CJ","LGV"),("JVH","XTN"),("QYL","98V"),("4G8","7FS"),("9CW","RQL"),("955","H3B"),("TLJ","D9H"),("V46","Q6Z"),("P97","3JC"),("YVQ","HR9"),("M7Q","WTZ"),("NPW","ZZL"),("B8L","WQ7"),("73B","99H"),("W5T","CCB"),("3YK","4N4"),("CW5","JSB"),("PH4","4HJ"),("K54","98X"),("1P6","G2M"),("MW3","Q67"),("CBP","F18"),("Q67","QMX"),("VHQ","N8G"),("1ZN","TLD"),("RVH","DV7"),("6KN","54H"),("7FS","B9R"),("JFL","821"),("H63","FRK"),("WQ7","RWK"),("R81","K8B"),("2SJ","H51"),("Y9S","37Y"),("LKC","DGR"),("P1V","8PP"),("MVX","ZNQ"),("8T3","V6P"),("JXX","JM5"),("8YN","JZN"),("1TJ","TZF"),("GWZ","FDK"),("S7Y","7SL"),("TK8","2NR"),("C1R","9SN"),("6YL","6YM"),("MJB","ZKY"),("2CC","GKH"),("C9W","R89"),("VY5","CZZ"),("1VD","62X"),("HKN","ZFH"),("YYX","892"),("CSK","CW2"),("734","3YG"),("HSW","PMJ"),("LDF","MDW"),("KMW","FHJ"),("7XT","LF6"),("KCR","48H"),("ZF6","DPS"),("9PP","TZC"),("7JK","KK2"),("QVG","KNW"),("4L6","4B7"),("S26","5ZG"),("R88","2LN"),("N6Y","18Y"),("B6Z","SS6"),("7C3","ZDQ"),("5LH","JMV"),("FGP","XSX"),("3KW","8HQ"),("COM","QR2"),("4QG","X81"),("ZMC","9S9"),("MND","HXM"),("WCY","BR6"),("HK4","2K3"),("MYY","5ML"),("KF8","YWH"),("DFV","LRL"),("XDS","7BL"),("K2K","KXT"),("L3F","BC4"),("9JG","9DH"),("SN5","47H"),("RLY","TBW"),("JYD","75Z"),("J4J","RZW"),("LTX","HYL"),("N8K","Q8V"),("6YY","XMS"),("6JD","WMX"),("3XH","WCC"),("1QP","QGQ"),("1WG","S45"),("KGN","93V"),("RV3","DXX"),("264","K2G"),("KZG","45H"),("G72","4RB"),("RC7","Y5X"),("LSS","QBK"),("CW2","6D9"),("968","ZNX"),("ZF8","Y61"),("G17","5RF"),("FT6","GKK"),("YBT","DGB"),("PP8","53Q"),("FV6","VLQ"),("JZM","HT6"),("YLC","BM6"),("VTC","8CY"),("56Z","BZK"),("QGY","PLN"),("5ZR","12S"),("DF4","4QQ"),("2CG","6CR"),("YWH","M64"),("HHF","HJX"),("LYF","YMJ"),("N98","QYL"),("7KT","G8Q"),("Y2D","GY7"),("8X3","8WT"),("58S","F69"),("QRD","Y6Z"),("N5L","VRY"),("PF9","RZJ"),("WSY","5LM"),("WKC","CQS"),("67L","516"),("HYL","MXY"),("ZNX","ZSF"),("GW4","XB3"),("TYP","JPV"),("7YZ","DYX"),("6YH","5VN"),("T2F","2QM"),("C4F","TXN"),("F8M","NRZ"),("S6K","L7T"),("YBG","JFQ"),("MGY","7RB"),("RJC","42P"),("91C","MGX"),("NCN","9NT"),("55Y","VXQ"),("M1S","7J3"),("9SP","9MS"),("FP8","97P"),("6WW","VB7"),("8M6","LJ2"),("N81","229"),("LKN","YH7"),("CLJ","1F3"),("V8Z","R14"),("C8Q","T5S"),("72T","QRZ"),("QBW","N82"),("WFY","8BJ"),("53B","3YK"),("2X8","HSW"),("VCV","3Z4"),("NVK","BPW"),("NNZ","5PQ"),("DZN","G1W"),("T27","X1F"),("3GG","2XH"),("G69","6KN"),("JM5","CM7"),("RHY","2XZ"),("T5M","443"),("WFQ","ZMC"),("MD8","DZN"),("JSH","RLL"),("64G","249"),("LFL","Y5P"),("SMQ","MKC"),("8ZR","VMB"),("X1M","NPT"),("21V","Y7K"),("2TX","D8X"),("S27","79W"),("LWF","9D1"),("JDM","LB7"),("YMF","3KW"),("LQ4","DWT"),("SG3","ZYY"),("2H3","F63"),("WKY","9G5"),("3SC","N3J"),("SPY","YK7"),("3LS","VNN"),("QN6","MLM"),("LZ6","FL6"),("4QQ","NNZ"),("7T6","5N5"),("3CS","FB7"),("XKF","ZQ3"),("HZH","W89"),("6SC","SJ3"),("45K","5ZR"),("XD4","PSJ"),("4DS","6PP"),("9VR","453"),("M41","JXY"),("4VD","JFX"),("3CP","KTL"),("WMX","XGQ"),("YSX","K54"),("CH3","KQV"),("RTP","B8L"),("K49","T4G"),("5QX","Y8V"),("5F8","Y5F"),("96T","PK8"),("CPL","2LD"),("LJH","LQ8"),("4RY","53B"),("R89","6YY"),("KHG","WC5"),("VQF","84L"),("NHG","GPR"),("PNH","CBP"),("SF8","DBV"),("XWF","M37"),("HHG","NTT"),("5LF","C8P"),("LFW","MW3"),("8TM","Y19"),("L6J","LL2"),("RP7","8YN"),("7KG","WFY"),("Y97","83C"),("GYJ","45D"),("D6Z","XPV"),("7J2","XP5"),("FWD","X7Y"),("BR6","Y97"),("MSV","1JL"),("MZ5","M3Y"),("2MJ","JYD"),("S6L","F8M"),("3Y8","V5R"),("3TQ","FBN"),("VRY","7NS"),("9YS","HYV"),("TBW","64G"),("NPX","C2G"),("Z1Q","YSX"),("ZZL","23X"),("C81","LY9"),("4KJ","4B3"),("HZ7","9XN"),("WC5","RZH"),("L7T","CLJ"),("R11","6K4"),("YGK","SM8"),("L35","YQS"),("YM4","Q7H"),("97M","53P"),("C8P","ZG8"),("6KT","V8F"),("4QQ","Z2B"),("8BM","XVH"),("98F","6RH"),("N82","62P"),("R6N","XWF"),("DFM","6MV"),("2WL","9RZ"),("T8B","9HT"),("BJG","GR7"),("FFF","8BM"),("1Z8","RHT"),("K7S","H28"),("3JC","DF4"),("P5P","WL9"),("CQ4","HPB"),("DV3","W43"),("B9K","DBH"),("3YG","WX9"),("Q5W","VZZ"),("VWW","QLM"),("9YJ","8XD"),("NCX","4GV"),("LGZ","169"),("WVR","Q14"),("PTM","1XY"),("PWH","QWV"),("VQK","7W5"),("ZTZ","7B9"),("GNN","2H3"),("D2N","8ZR"),("3HH","SWT"),("3NV","ZJ6"),("GR7","HLG"),("QSC","BJG"),("N8G","6TS"),("82K","51T"),("ZFN","D2N"),("1J4","CVV"),("ZL2","5VB"),("Q14","Y1D"),("575","9L6"),("67L","KJ4"),("NRR","LR4"),("T4G","GQB"),("D95","JFL"),("XWD","HZB"),("SY5","6Y4"),("HT6","6FK"),("DQR","G5N"),("F63","Q61"),("NFY","Z12"),("VZM","ZDZ"),("3G5","RSQ"),("9M2","3GG"),("1H4","Q3Q"),("WYP","4TP"),("99L","SLF"),("PST","YMF"),("HXM","RHY"),("CNL","DLS"),("4XQ","6T4"),("QMS","63P"),("2LF","X4C"),("T9K","DFV"),("TZG","KF8"),("4ZZ","C6Z"),("8KZ","2LH"),("8ZC","9NN"),("42D","T4V"),("5M5","R6N"),("XCF","Q76"),("BPP","FZX"),("HBM","G72"),("4J9","RLD"),("DRD","56Z"),("MBL","X13"),("QS2","8X7"),("87R","CJY"),("WYP","3Z2"),("Q8V","QSG"),("VMX","NPW"),("11V","RPT"),("Q7S","FP8"),("L8Z","CVF"),("4L3","JLF"),("G5F","MZN"),("24F","JTV"),("6K4","GHN"),("4RC","G7Q"),("LYF","6KQ"),("JWX","FRR"),("CJY","C9W"),("DGB","J2C"),("TQF","DRD"),("SG3","57K"),("8JT","CKN"),("ZNS","L8T"),("VGS","59B"),("C6Z","VV4"),("386","5BD"),("7HB","8K7"),("D4Q","GV5"),("4H1","2BH"),("SVB","T5M"),("8X4","LHJ"),("C8P","GJ4"),("6SK","42D"),("MDW","YHK"),("HN9","3CS"),("N41","7ND"),("L45","67L"),("B32","B23"),("P8V","RHB"),("C1R","2WL"),("D8T","444"),("ZVZ","2X6"),("GV1","VY5"),("H7H","ZM7"),("ZN3","DV5"),("3MC","L8Z"),("WF1","JKG"),("ZNQ","4ZR"),("TMK","MGY"),("VD6","61Q"),("8XX","MK3"),("7K5","XN5"),("GM6","F86"),("KBF","X6X"),("12S","Y9S"),("DXX","LJH"),("VQ7","FF8"),("KWP","YC9"),("VBH","PYW"),("25Y","2Y1"),("7SL","264"),("7PQ","T8B"),("TJ9","5J8"),("NQ8","MC1"),("KF6","NYH"),("FTL","PRX"),("JT4","9CW"),("QPK","FGP"),("DV5","1CW"),("XQY","WBC"),("FRR","MYY"),("PRQ","2MZ"),("RPP","G7W"),("249","CQZ"),("27J","7PT"),("B5P","ZL2"),("6WW","HY8"),("FZX","NQC"),("CFC","MK4"),("5VN","15T"),("KNW","CHK"),("ZJS","433"),("CR5","5NQ"),("T88","58S"),("L27","NSY"),("LC3","KCR"),("VB7","FFD"),("GKK","W2X"),("WXM","9TT"),("1M2","VLV"),("5BD","3CP"),("HBW","7J2"),("XTW","L64"),("JCX","XGL"),("34K","6YH"),("9K3","5LH"),("4V2","24F"),("JFQ","5WF"),("MKC","TMK"),("6Z3","WDH"),("JLQ","SYX"),("S38","9HZ"),("63T","FW6"),("XNH","VMX"),("NXF","TBG"),("XKN","6DL"),("T6J","GN8"),("LCX","VN9"),("3LS","GM6"),("TD8","1TJ"),("4ZZ","HRV"),("365","YPT"),("6T9","6NF"),("HX6","Y22"),("R19","4BF"),("B15","ZC5"),("663","NN7"),("Z4C","GQT"),("T5S","66C"),("7SL","L6T"),("39W","QQC"),("6Y1","K1S"),("PK8","RQP"),("5RF","24P"),("MK3","WM7"),("RGB","WXP"),("854","XKF"),("CKN","WD1"),("R6Q","8VD"),("BK3","6FH"),("4LT","1YK"),("9FJ","HBW"),("Y9B","KSG"),("2MQ","7ZM"),("FYJ","T32"),("17L","M1Y"),("XMS","1P6"),("12S","C22"),("7F3","KF6"),("6Y4","86S"),("ZJD","JWX"),("5ML","Z5D"),("8YZ","F5D"),("YC9","MD4"),("PQJ","C9N"),("23X","LC3"),("5SP","FYJ"),("Z48","YOU"),("9MS","LQ4"),("5ZG","G4T"),("VW8","SN5"),("DYD","HN6"),("6DG","G82"),("P8B","LYG"),("HXY","KHG"),("GN8","9Z7"),("C2Y","QSC"),("4PN","LJN"),("7CW","HB4"),("9JM","YYX"),("13F","SRP"),("HPB","5F8"),("K5B","LFL"),("62X","FGC"),("2LD","D7V"),("4BZ","6YL"),("WTZ","M33"),("K2J","R5Q"),("MRW","X5R"),("M3G","CPL"),("BMP","WT8"),("XPH","BQ3"),("B15","X2Y"),("XN5","MVX"),("Z2D","B15"),("1JL","TS3"),("9DH","2C2"),("TVY","M3G"),("62P","C4F"),("4CR","KXM"),("4GX","4L3"),("YVQ","TZX"),("1H4","TZW"),("VP4","CFW"),("NM9","Q7S"),("LRH","TSW"),("4M2","H9W"),("WLD","DWG"),("8R4","4XQ"),("6FH","LX6"),("4G8","9FY"),("QPK","S26"),("YVY","N98"),("Y4T","LDY"),("YHK","SJB"),("DWG","RPP"),("16R","XQY"),("W43","MHQ"),("9NN","C2Q"),("XFM","S6K"),("QVS","6M3"),("L45","WZR"),("K3X","BLF"),("Q3Q","L9T"),("6M3","TTS"),("SVN","VTL"),("CRK","2LF"),("QT1","4H1"),("V6K","WKC"),("7ZM","1KD"),("75Z","62H"),("T7R","Q99"),("QLS","RVC"),("SRG","J48"),("HSQ","89W"),("1KQ","NRR"),("L43","P8B"),("ZZV","591"),("HB4","VP4"),("F8Z","X39"),("BTQ","GQM"),("ZDQ","QN6"),("B6F","6NZ"),("X5R","1MT"),("JP2","T9K"),("DW6","W77"),("7YL","ZTZ"),("CJV","PX7"),("784","B9P"),("NJL","J9K"),("W65","TSS"),("9YJ","GW4"),("BVX","K7S"),("HLG","6CV"),("WF4","5M9"),("53P","WLD"),("4B7","YVV"),("LY9","8RH"),("K2G","D6Z"),("WWT","Y6G"),("4XJ","1T7"),("14L","K2J"),("M75","6Z3"),("4RC","R11"),("Y1D","F7Q"),("H5J","KQN"),("NWT","7QQ"),("KQV","K3F"),("9M2","QS2"),("K93","B86"),("ZN9","YBG"),("LTV","KZW"),("5VB","N4J"),("WVQ","LXB"),("1WG","PQJ"),("516","NXF"),("WZ1","ZFN"),("K8B","1MW"),("ZFS","75B"),("YT8","1VC"),("62V","DTQ"),("RLL","CBN"),("RNW","K9K"),("S6F","CJV"),("23X","S81"),("LFC","GXS"),("K4K","GT4"),("5RD","FK9"),("QC2","NQJ"),("QMX","R9J"),("HHF","MD8"),("Y1M","D2R"),("8R1","PTM"),("GY7","KRV"),("DWT","R6H"),("MGX","45K"),("XGL","53S"),("VFM","9JG"),("N5Y","VFM"),("X39","C81"),("QTQ","LYT"),("JXX","MSV"),("MMJ","PZY"),("L7N","NQ8"),("Q79","ZZN"),("LJP","5QR"),("X2Y","6QF"),("37Y","8TM"),("X81","7GT"),("CP8","V8H"),("QFK","3TQ"),("6QS","TK8"),("B93","JB5"),("WC6","RJC"),("ZD4","WZ1"),("XVX","QFK"),("4N4","4QG"),("189","QVG"),("GT4","LD7"),("3Q3","BHB"),("BGF","Z5S"),("KDY","9YM"),("9NT","QLS"),("FNP","NS3"),("8WT","NXR"),("XGQ","PP8"),("85Z","24K"),("CVF","RV3"),("GBV","D8T"),("YPN","FFF"),("RVC","B28"),("N4N","TGZ"),("G6N","KDY"),("8QR","511"),("45D","YR9"),("8X6","4N5"),("96Z","QGG"),("TGZ","WYP"),("KWF","WKY"),("QK9","TSP"),("GJC","L62"),("7J3","PNH"),("TF8","XPG"),("54H","365"),("VLV","V94"),("729","2MJ"),("YQ1","GV1"),("TZF","8YX"),("BC4","562"),("DK4","4Y1"),("R3D","CRK"),("Y3S","1Y9"),("4L3","1Z8"),("QQY","KQ9"),("PLN","HK4"),("2LH","G22"),("3YZ","9M6"),("TS3","5SP"),("LN6","M41"),("VT6","DN3"),("XVH","XHN"),("YT8","4NT"),("MN6","784"),("1W8","L6J"),("V8F","2K7"),("5N5","7M1"),("M27","25Q"),("HYV","CD4"),("6YM","TXQ"),("MPC","6SK"),("9D1","BTQ"),("QRZ","HBM"),("RWS","CB8"),("T4S","ZNS"),("54W","PCB"),("JMV","D66"),("WT8","2FB"),("Z4T","4VD"),("RF6","72T"),("Q7H","97M"),("84L","TQ3"),("6MV","SBG"),("45H","5XR"),("33M","F35"),("6NZ","JZM"),("HYV","YQM"),("9MY","B6F"),("1TX","KQ3"),("T32","8XX"),("V68","QKR"),("WLD","SSX"),("YJR","Y6L"),("24K","NPX"),("73M","TCB"),("FR4","LSS"),("BRS","WCY"),("Q5H","R63"),("LWY","FGW"),("KQ3","LSY"),("7KT","YX3"),("GLT","HWP"),("FFD","QPK"),("4TP","8XM"),("FRX","XFM"),("JPV","884"),("JFX","9VR"),("ZDZ","VW8"),("G9F","R5S"),("TZF","H63"),("62C","189"),("N6T","ZFR"),("6D9","7PQ"),("KXS","4GX"),("YCW","WVQ"),("2X6","WCQ"),("2MQ","2J8"),("HG4","C3F"),("BZ7","J3T"),("P2Q","JDM"),("TSW","KBF"),("KQ1","8T3"),("CCL","RSP"),("C87","Z3Z"),("75B","C7Y"),("TYL","7NF"),("JCF","235"),("N1T","FYM"),("MHQ","YBT"),("L3G","R81"),("4VD","N1T"),("ZM7","YMY"),("9G5","YZ2"),("MC1","R2P"),("LL2","YCW"),("SKN","BPV"),("979","14L"),("N8G","SMQ"),("WHD","7SK"),("ZKY","P8V"),("42P","1JB"),("57K","KXS"),("J1G","7H6"),("9S9","2GY"),("YWG","9LX"),("HWP","T81"),("7G1","88C"),("T67","M75"),("M37","TPD"),("24P","QT1"),("F86","NCX"),("RWK","QJP"),("RSP","65G"),("NYY","QMP"),("GS6","JQ8"),("X1Z","R6Q"),("181","62V"),("4GV","P4C"),("T5Y","CCL"),("2J8","CNH"),("9RZ","LN6"),("NRQ","3Q3"),("SYX","L6K"),("GWK","VQK"),("9Z7","63T"),("T4Y","1W4"),("6Y4","9M2"),("47H","8M6"),("X77","ZF8"),("KWM","4BZ"),("53S","V17"),("21R","QDN"),("2G3","N7Z"),("88V","FR9"),("58W","7YZ"),("TCB","DG3"),("L8T","7H2"),("QY8","X1X"),("4QJ","KPL"),("C22","N9Y"),("FR9","HTP"),("WGL","G38"),("CM7","14W"),("6CV","CR5"),("X13","K6Z"),("XHN","31H"),("93V","HSQ"),("WZR","LN3"),("Q7Z","6T9"),("G22","LCX"),("N1T","FR4"),("58Y","3Y8"),("K3F","GHV"),("RSQ","W5T"),("LRL","6GN"),("6DL","F95"),("7VG","1RJ"),("KSG","49Q"),("8HQ","4J9"),("Q99","9DZ"),("H2P","559"),("FYJ","L7F"),("NTT","D4Q"),("ZQ3","6WW"),("T7W","8R4"),("8ZX","K5Q"),("Y2K","Y9B"),("YVV","6JL"),("NN8","FV6"),("F5X","XT7"),("T4V","T5Y"),("63P","3GN"),("TXQ","QTQ"),("Y19","2RN"),("FW6","QRD"),("8QB","ZL5"),("N4J","P97"),("KQ9","ZD4"),("BGF","SR3"),("HJX","3HH"),("WXN","KPX"),("WWB","Z7B"),("14W","2X8"),("3MD","8DX"),("LJ2","WQD"),("GLT","1DF"),("4HJ","7KT"),("DV7","8FW"),("235","YJR"),("GC2","H9V"),("P8B","ZJS"),("Z4T","KD7"),("CZY","SF5"),("93L","PF9"),("JJP","NJL"),("31H","WXM"),("CZZ","9QX"),("DKS","NGJ"),("N58","QRS"),("V36","SR6"),("RJK","H5J"),("VKF","4L6"),("SWZ","GYJ"),("9LX","Y1M"),("591","RZ2"),("LGZ","7JK"),("98X","8X6"),("G5N","ZF6"),("2K3","98F"),("T3V","WWB"),("GHY","TX7"),("JFQ","VGH"),("RHB","2BD"),("82N","782"),("Q2M","T2G"),("Q8F","9K3"),("62V","JJP"),("T1F","PJT"),("SS6","TD1"),("TN3","6QS"),("L6K","2KR"),("CKT","QY8"),("BRG","Q54"),("TGB","JCB"),("LGV","S38"),("G7N","LKC"),("PX7","VWW"),("TYL","742"),("5M9","TVY"),("1HF","CHW"),("T46","TD8"),("ZP4","4RY"),("WBC","XTW"),("8XM","CNB"),("VGH","GHY"),("BQ3","NCN"),("LSY","SVC"),("CHK","V68"),("KYD","LWY"),("2GY","TK3"),("HFT","8VF"),("MZN","4FR"),("JTV","L3G"),("7FS","Q2H"),("D98","MPC"),("DB6","J77"),("Y8V","WNF"),("B86","2LT"),("MDW","T7W"),("LB7","3NW"),("DYX","GYV"),("S6M","S89"),("GR7","GNN"),("5PQ","5QX"),("XSX","Q5W"),("7ND","YVQ"),("JDX","1QP"),("KR6","3XH"),("TPD","FT6"),("KPX","HZ7"),("VM1","8JT"),("229","YM4"),("538","M65"),("KTL","N81"),("844","21V"),("453","21R"),("HR9","NKW"),("GZ2","QK9"),("6KS","YCS"),("2HF","4DS"),("WMX","X1Z"),("4J9","ZJ8"),("FB6","KZG"),("L9T","L27"),("7NF","ZFS"),("6HL","XKN"),("V2T","WGL"),("TJD","HYM"),("1Y9","8JY"),("884","91C"),("4RS","3NV"),("GQJ","8Z3"),("NYX","S7Y"),("BRS","XJR"),("G8Q","QGT"),("5LM","5V9"),("TLD","3D5"),("R63","VLH"),("SRP","82N"),("K6Z","GPH"),("1RJ","YT8"),("21L","RNW"),("VV4","XVX"),("LR4","34R"),("MK4","X1M"),("Q2H","YVY"),("37X","5S6"),("8ZC","VT6"),("F18","Z4T"),("V8H","YX8"),("JT6","H6Y"),("8DL","1ZN"),("MZN","FCQ"),("5N5","NDL"),("L3T","3SC"),("XGQ","C5Q"),("BW5","F8Z"),("82N","N5Y"),("48H","MJB"),("J2C","SWZ"),("8XD","T3V"),("7B9","ZM9"),("66C","CFY"),("GMW","55Y"),("CNH","2CG"),("14S","R88"),("RZH","P5P"),("6QF","L9L"),("YQM","4RC"),("4B3","9MY"),("NXR","VFY"),("Y6Z","1TX"),("V46","WFQ"),("1N9","D98"),("TZC","KGN"),("N31","3X5"),("YBT","T88"),("1T7","FFC"),("TSP","5PF"),("VXQ","3MC"),("9MT","CFC"),("Y5F","MC8"),("2LF","DCR"),("Z7B","N4N"),("KXM","6QK"),("4Y4","VHQ"),("3BH","61J"),("Z5D","NM9"),("GY7","2B7"),("YMJ","YWG"),("RW8","B6M"),("YPN","GX2"),("R5S","4CR"),("KXT","QB8"),("GFR","RWS"),("C2Q","M3D"),("89W","YVF"),("X1X","BQW"),("FCY","YS1"),("Z3Z","538"),("F5D","3K3"),("P68","FWD"),("C2G","TJD"),("HY8","T2F"),("DLH","CV9"),("CFW","FRX"),("9SN","DJM"),("1VC","7KG"),("LDY","2SJ"),("D6T","SF8"),("YQM","T67"),("296","5YV"),("F18","KR6"),("C5Q","738"),("Q6Z","SY5"),("1NN","LGZ"),("SSX","6GT"),("738","PH4"),("LYT","JP2"),("1W4","K5B"),("N31","YPN"),("KVX","QJ8"),("444","97J"),("CVW","YL6"),("S81","RC7"),("KK2","4RS"),("KWP","BK3"),("229","BGF"),("M3Y","959"),("R9J","18D"),("NDL","T4S"),("6PJ","KY3"),("2FB","7XT"),("6K7","WN4"),("821","9VN"),("7BM","DYD"),("NS3","T6J"),("9HT","JDX"),("MVB","GQJ"),("7KG","5RD"),("NXR","N5L"),("34R","ZVZ"),("KVQ","HFT"),("6B3","DV3"),("1MT","MGB"),("7NK","J2L"),("QWV","36C"),("2M1","NWG"),("59B","BZ7"),("7KJ","GWZ"),("9DZ","CP8"),("87T","SAN"),("5WF","37V"),("B9R","G5F"),("RHT","VRC"),("P27","TBJ"),("G8S","KYD"),("78S","FB6"),("N9Y","BSF"),("FWP","1W8"),("9MS","968"),("TWM","LJP"),("VSC","VQF"),("NQJ","58W"),("8X7","RK9"),("FRK","H7W"),("2XZ","YMC"),("FGC","V36"),("NGJ","GL9"),("6Z2","X3X"),("892","16R"),("RZW","2DP"),("QSG","6KS"),("B28","HWT"),("J2L","TN3"),("2ZC","JSH"),("75Q","NHG"),("DTQ","RGB"),("8BJ","MRW"),("NKW","XMN"),("WXP","ZLS"),("959","RDN"),("S89","VKF"),("8Z3","BP1"),("RQL","KVX"),("KD7","DQR"),("H9W","LTZ"),("PYW","MBL"),("7SK","6SC"),("MLM","3LS"),("433","FNM"),("DJM","LDF"),("7H3","DY5"),("GPH","2G3"),("N3J","ZDW"),("QR2","SDX"),("WKZ","4XJ"),("2K7","WKZ"),("7PT","HMN"),("41X","2M1"),("K49","27N"),("1CW","K9W"),("S8S","4G8"),("5PX","93L"),("C7Y","663"),("MQT","HG4"),("NYH","L3T"),("YS1","2MQ"),("7QQ","GMW"),("F7Q","WF4"),("H6H","DKS"),("NQC","KWP"),("KPL","B7L"),("L7M","8YZ"),("P7T","7D9"),("PVQ","F5X"),("FHJ","GJC"),("LF6","273"),("L64","S6L"),("42P","9SP"),("RN8","C8Q")];

type Sstr = &'static str;

fn steps(g: &HashMap<&str,Vec<&&str>>, node: &str, rec: usize) -> usize {
  match g.get(node) {
    Some(v) => v.len() * rec + v.iter()
      .map(|k| steps(g, k, rec+1))
      .sum::<usize>(),
    None => 0,
  }
}

fn part_one() -> usize {
  let g = INPUT.iter()
    .map(|(k,_)| {
      let v = INPUT.iter()
        .filter(|(a,_)| a == k)
        .map(|(_,b)| b)
        .collect();
      (*k,v)
    })
    .collect::<HashMap<_,_>>();
  steps(&g, "COM", 1)
}

fn find_neighbors(node: Sstr) -> HashSet<Sstr> {
  INPUT.iter()
    .filter(|(a,b)| *a == node || *b == node)
    .map(|(a,b)| if *a == node { *b } else { *a })
    .collect()
}

fn find_path_len(here: Sstr, goal: Sstr, visited: &mut HashSet<Sstr>) -> Option<usize> {
  if visited.contains(here) { return None; }
  visited.insert(here);

  if here == goal { return Some(0); }

  find_neighbors(here).iter()
    .map(|v| find_path_len(v, goal, visited))
    .find(|o| o.is_some())
    .unwrap_or(None)
    .map(|i| i + 1)
}

fn main() {
  let now = Instant::now();
  let part_one = part_one();
  let part_two = find_path_len("YOU", "SAN", &mut HashSet::new()).unwrap() - 2;
  println!("Part one: {}", part_one);
  println!("Part two: {}", part_two);
  println!("Time: {}ms", now.elapsed().as_millis());
}