oj.uz

Submission #993759

# Submission time Handle Problem Language Result Execution time Memory
993759 2024-06-06T11:45:36 Z TimDee Capital City (JOI20_capital_city) C++17
11 / 100
 3000 ms 95584 KB 
//             _
//   ^ ^      //
// >(O_O)<___//
//   \ __ __  \
//    \\ \\ \\\\

/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⠷⢛⠩⣡⠦⢂⢂⢂⠂⡂⢂⢐⢀⠂⠄⡂⠄⢂⢐⠠⢀⢂⢐⢀⢂⠄⡂⡂⡂⠢⠡⡂⠪⡐⢅⠪⣙⢛⡻⡻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣯⣿⣯⣿⣯⣿⣯⣿⣽⣿⣺⡫⣿⣽⣯⣿⣽⣯⣿⣽⣯⣿⣽⣯⣿⣽⣯⣿⣽⣯⣿⣽⢾⣻⣵⢞⣴⠟⡡⡊⠄⠢⢐⠨⢐⢐⢐⠠⢁⠅⡂⠌⠔⡐⡨⢐⠐⡐⡈⡢⢑⢐⢅⠪⡘⢔⠌⡪⢐⢅⠇⡎⡪⡪⣚⢮⡻⡾⣿⣾⣿⣽⣯⣿⣾⣿⣾⣿⣽⣿⣽⣯⣿⣽⣯⣿⣽⣯⣿⣽
⣿⣻⣿⣽⣿⣽⣿⣻⣿⣽⣞⢽⢽⣿⣟⣿⣿⣻⣿⣟⣿⣿⣻⣿⣟⣿⣟⣿⣻⣯⣯⣷⣿⣻⣚⣞⠵⡩⢂⠊⠌⠨⡐⠨⢂⢂⠢⠨⡐⢔⠨⡘⢌⢐⢐⠔⡡⢂⠢⠪⡨⡢⢱⠨⡊⢆⢣⢪⠢⢅⠣⡣⡣⡱⡑⡕⡯⣿⣾⢿⣾⣿⣻⣿⣯⣿⣾⣿⣯⣿⣟⣿⣟⣿⣿⣻⣿⣟⣿⣟
⣿⣿⣟⣿⣽⣿⣻⣿⣻⣿⣻⣿⣻⣯⣿⣿⣽⣿⣯⣿⣿⣽⣿⣯⣿⣿⣻⣿⢿⣻⣿⣻⣿⢻⡝⡪⡑⢌⢐⠁⠌⡂⡊⢌⢂⢂⠅⢕⠨⡂⢕⠨⡢⡑⢔⢑⢌⠆⢕⢑⢌⢪⢊⢎⢎⢎⢪⡸⡸⡱⡱⡌⡎⣞⢼⢸⢪⢮⡻⣿⣿⣾⣿⣯⣿⣿⣽⣷⣿⣟⣿⣟⣿⣿⣽⣿⣯⣿⡿⣟
⣿⣯⣿⣿⣟⣿⣟⣿⣟⣿⣟⣿⣟⡯⣿⣯⣿⣯⣿⣯⣿⣯⣿⣯⣿⣟⣿⡿⣿⡿⣟⣯⡾⢣⢑⠌⡐⡐⡐⡐⠅⡂⡪⠐⡐⠔⡅⢕⠨⢌⢢⠣⡢⡱⢡⢃⢎⠜⡨⡊⡆⢎⢪⡪⡎⣞⡜⡼⣸⠸⣜⢼⢸⢬⢳⢳⡱⡱⢕⢇⠯⣷⣿⣯⣷⣿⣟⣯⣿⣿⣻⣿⣿⣽⣿⣽⣿⣽⣿⣿
⣿⣿⣽⣾⣿⣟⣿⣿⣻⣿⣟⣿⣷⢿⣟⣿⣽⣿⣯⣿⣯⣿⣯⣿⣯⣿⣻⡿⣟⣟⣯⠷⢩⢂⢂⢊⢐⢐⠰⡈⡂⡪⠠⡑⡌⠕⡌⡢⢣⢑⢅⢇⢪⠸⡰⡱⡘⡌⡆⡣⣪⢪⢪⡪⡎⣗⢵⢝⡮⣣⡣⡫⡺⣜⢵⡓⡽⡸⡸⡱⡹⡘⢾⣽⡿⣯⣿⣿⣟⣿⣟⣿⣾⣿⣯⣿⣿⣽⣿⣷
⣿⣾⡿⣟⣷⣳⣻⣿⣻⣯⣿⣿⣻⣿⣿⢿⣟⣯⢯⢯⣿⣿⣽⣿⣻⣿⣻⣿⣿⢿⢫⢘⠔⢐⢐⢐⢐⠔⠡⢂⢒⢌⠪⡢⡑⡅⢇⢊⢆⢣⢱⢸⠸⡘⡌⣆⢳⢨⢪⢪⢪⡪⣣⢫⢞⢜⢕⢗⢝⢮⢺⡸⡜⢎⢮⢺⢜⢜⢜⢜⢜⢌⢇⢟⣿⣿⣟⣷⣿⡿⣟⣿⣿⣾⢿⣻⣾⣿⣷⣿
⣾⡿⣿⣿⣿⢿⣽⣿⣟⣿⣿⣽⣿⣽⣾⣿⣿⣿⣽⣽⣿⣽⣿⣽⣿⣟⣿⣯⠟⢕⢡⢑⠨⢐⢐⢐⠔⠡⢁⠢⡱⢰⢑⠱⡐⡕⢅⢕⢱⢱⢱⢱⠱⡱⡱⡱⡕⡕⡵⡹⣜⢸⢸⢸⢱⢕⢕⢕⢭⢳⡱⡕⣝⢜⢜⡜⡎⣎⢎⢎⢜⠜⣜⢜⢷⣿⣻⢿⣻⣿⣿⣿⣾⣿⣿⣿⡿⣿⣾⣿
⣾⣿⣿⢿⣾⣿⣿⡽⣿⣻⣽⣿⣾⣿⢿⣻⣽⣾⣻⣿⣽⣿⣯⣿⣯⣿⠽⡂⡣⢑⠐⢄⠕⠡⡐⢌⠌⢌⠢⡱⠸⡐⡅⡣⡱⡸⡐⡕⡱⡑⡅⡇⡇⡣⡣⡫⡣⣪⡎⡇⣇⢣⢱⢱⢱⢱⢑⢕⢕⢕⢕⢕⢕⢕⢕⢜⢎⢮⢢⢣⠱⡑⡜⡵⡱⡻⣿⣿⡿⣿⣾⣿⣾⣿⣾⡿⣿⣟⣿⣾
⣻⣯⣿⣿⢿⣻⣽⣿⢿⣿⢿⣻⣗⢯⡻⡻⡿⣿⣿⣻⣯⣷⣿⡷⣟⣍⣪⢴⡜⡐⢌⠢⠨⡨⠨⡐⢌⠆⡕⢜⠡⡱⠨⡢⡣⣊⢢⢱⠱⡱⡱⡱⡡⡣⡣⡣⡱⣯⢿⡜⡔⡕⡅⡇⡇⡕⡕⢕⢅⢣⢣⢣⢣⢣⢣⠣⡣⡣⡣⡣⡩⡊⢆⡻⣽⡜⣽⣷⣿⣿⣷⣿⣷⣿⣷⣿⣿⡿⣟⣿
⢯⣞⣮⣻⡻⣿⣿⢿⣿⢿⣿⣿⢗⢧⡫⡮⣻⣿⣽⣿⡿⣟⣿⣿⣻⣽⡛⢕⣨⡬⢂⢐⢑⠠⠡⡘⢔⠱⡘⠔⡑⢜⢨⠪⡒⡔⡸⡰⡱⡱⡑⡕⡌⡎⡜⡰⡽⣯⢷⢯⡪⡪⡸⡨⡪⡸⡸⡸⡸⡘⡜⡌⡎⡜⡔⡕⢕⢕⢕⠕⡌⠌⡆⢇⡻⣟⣎⢷⣿⣷⣿⣷⣿⣯⣿⣯⣷⣿⣿⣿
⢕⣗⣵⣳⢽⣟⣿⣿⡿⣿⣿⣽⣏⢗⣝⢮⣳⣿⡿⣷⣿⣿⣿⣻⣯⢗⣮⡏⡃⡂⡂⠔⡡⠈⡔⢌⠢⡑⠅⢅⠕⠅⡢⡣⠣⡊⢔⠕⡜⢜⢜⠜⡌⡎⡊⣞⣯⡯⡿⡽⣎⢎⢆⢣⢱⠸⡰⡱⡸⡐⡌⡊⡎⡆⡕⡜⢌⢎⢆⢇⢇⠕⠨⢪⢪⢻⢗⣟⣿⣯⣷⣿⣯⣿⣯⣿⡿⣟⣿⣽
⡳⡵⣳⣳⣻⣿⣻⣷⣿⣿⣿⣽⣾⣿⣾⢷⣿⣟⣿⣿⣟⣷⣿⣽⢾⢛⠣⡑⡐⡐⡐⡐⠄⡕⢌⠢⠑⢌⠊⢔⠡⢡⢃⠎⢕⢑⢸⢘⢜⠜⡔⡕⢅⠇⢮⣻⣞⣽⢽⢯⢷⢕⠥⡑⡅⢇⢕⢜⠔⡅⡣⢕⢌⠊⢎⢜⠔⢅⢇⢕⢅⢣⠡⠡⡓⣝⢽⣗⣿⣟⣿⣿⣽⣿⣯⣿⣿⣿⣿⣿
⢜⢽⡺⣿⣿⣻⣿⣟⣿⣷⣿⢿⣻⣽⣿⡿⣿⣽⣿⢷⣿⢯⣞⣪⡦⣱⢕⢐⠅⡊⠔⢀⠣⢊⢠⢂⠅⡂⡑⡐⠅⡪⡂⠪⡪⡨⠢⡣⡱⡑⡕⢜⢸⢨⢛⢚⢚⠚⠫⠫⠫⢓⢅⢇⢊⢪⠢⡱⡑⢌⢊⠔⡐⡱⡑⠜⡜⡌⢎⢪⢊⢆⠣⡑⡌⡌⡺⢜⡽⣻⢯⣿⣯⣷⡿⣿⣾⣿⣾⣿
⡸⣜⢼⢹⡫⡿⣟⣿⣿⣽⣾⣿⣿⣟⣯⣿⣿⣿⣽⣿⣯⢿⣾⢟⢅⠫⡐⢅⠪⡌⡐⠄⡃⡢⡑⠌⢊⢂⢎⠌⡢⠱⠀⢱⠨⡢⠱⡱⡘⡌⡎⢜⠰⡸⣝⢞⢜⠎⢎⢪⢸⢰⢱⡸⡨⡂⢇⢪⢘⢌⠢⠁⠈⡀⠁⠑⠨⡊⡪⡸⡐⢅⠪⢰⣱⡽⡌⣮⣮⣎⡯⣞⣷⣿⡿⣿⣿⣾⣿⣻
⡺⣪⣷⣷⣯⣮⢇⣗⢽⣿⣻⣿⡷⣿⡿⣿⡿⣾⣿⣻⣞⣟⢏⢊⡢⢱⢘⢌⢎⠆⡊⡐⡐⢌⢊⢊⠊⠌⠂⣊⡤⢥⢌⠐⢕⢌⠪⡢⢣⢱⠸⡨⠊⠊⠂⠁⠈⠈⡁⠐⢡⢳⢵⢝⡦⡣⡣⡑⡢⠪⡀⡊⢔⢌⡮⢀⢐⠸⡰⡱⡑⡰⡁⡣⣑⡻⣻⣜⡽⡿⣿⣷⣮⣗⣿⣿⣷⣿⣟⣿
⢽⣽⣻⣯⣿⣟⣮⣺⣺⢿⣻⣯⣿⡿⣿⡿⣟⣿⣾⢿⢝⢅⢧⠱⡱⡑⡕⠌⡎⠔⡐⡐⢌⠂⢅⠢⠠⠁⢰⠣⡪⡪⡨⠣⡑⢔⠱⡘⡌⢆⢣⢊⠀⡐⠠⣑⠡⣱⢸⢼⡰⡹⣮⣻⣺⢽⣎⣎⢌⠇⡎⣌⢫⠜⡊⡔⠄⢕⠨⡪⡢⠢⡱⡘⡔⣷⢹⣷⢿⣿⢿⣷⣿⡿⣷⡽⣷⣿⡿⣿
⢿⢿⣾⣞⢿⣻⣯⣿⡿⣿⣿⣿⢿⣿⢿⣟⣿⡿⡞⣍⣾⣻⣣⢗⢕⢱⢡⠑⠌⣂⠢⡨⠂⠌⠄⠌⢀⠈⢸⢨⢲⡙⠌⠌⢌⢆⢣⠱⡘⡌⡆⠕⡠⡈⠣⡙⡝⡪⡞⣏⢮⣞⣗⣗⡽⣽⣺⣗⢷⡱⡸⣘⢮⡳⡕⡕⡅⢕⢸⢸⢐⡑⠴⡑⡜⠽⣗⣿⣽⢿⣿⣟⣷⣿⣿⣿⡽⣿⡿⣿
⢿⣽⣳⡯⡯⣿⣟⣿⡿⣿⣿⣾⣿⣿⡿⣯⣿⠏⣮⣾⣳⢯⢣⢣⠣⡱⢡⠩⡊⢔⠡⠨⠨⡈⠄⡁⠠⠐⡀⠓⡜⡎⢕⢁⢂⢪⠰⠡⡣⢪⠨⡊⢜⣜⢖⣔⢦⣳⢽⣺⢽⣺⣺⢮⣻⡺⡮⡯⣗⣟⣜⢮⢎⡞⡮⡪⡂⢕⢸⠰⡐⣯⢯⢾⣼⣮⣮⢺⣿⢿⣻⣿⣟⣿⣯⣿⣟⣿⣿⣿
⢸⢹⢺⣻⢭⡻⣟⣿⡿⣿⣷⣿⢿⡾⣟⣯⢏⢮⠳⡣⢣⢪⢪⠢⡑⡕⡡⢑⢌⠢⡊⠌⡂⠂⠅⠄⡑⡐⡈⡐⠈⢝⢆⢅⢂⠂⡣⡃⡪⡂⢇⠪⡸⣪⡳⣕⡯⣺⢽⣺⢽⣳⢯⣻⢮⡫⡾⢽⡻⡺⣺⣝⡯⡯⡯⣎⢂⠪⡪⡸⢐⢿⣿⣻⣾⣯⣿⡕⣿⣿⣿⣟⣿⣟⣿⣽⣟⣯⣷⣿
⢱⢨⠢⡊⡪⡻⣯⣟⡿⣿⢷⡿⡯⡿⡳⡫⡪⡊⡎⡎⡎⡎⢆⢣⢣⠱⡈⡢⡊⡢⡑⡁⡂⠅⠅⢂⠂⡐⠐⠨⠈⠄⠃⢆⢐⠄⡱⠰⡐⢅⢣⠑⡌⡞⡮⣗⢯⣫⣗⡯⣟⡾⣽⣺⣳⡱⡡⢕⢱⢡⣷⣳⢯⡯⣯⠪⡐⡱⡱⡸⠨⣟⣿⣿⣻⣿⣻⡧⣿⣿⣾⣿⢿⣻⣿⣟⣿⣿⢿⣿
⢸⠸⡸⡨⢢⢊⢢⢑⠍⡝⢝⠞⡪⡚⡜⡜⡜⡜⡜⢜⢜⠨⡪⢸⢐⢕⢘⢌⠢⠢⡱⠐⠄⠅⡊⠄⢂⢠⡑⠈⠐⡈⢀⣆⠔⠈⢂⠇⡊⡢⡑⢅⠪⡪⡫⡾⣝⣞⡮⡯⣗⡯⣗⡯⡾⣝⡮⡧⣳⢯⢾⣺⢯⣻⡪⡁⠢⢪⠪⡊⡪⢿⣯⣿⣟⣿⣯⢿⣟⣿⣾⣿⣿⡿⣟⣿⣯⣿⣿⣿
⠰⡑⡅⡣⠣⡊⡢⢣⢑⢜⢔⢕⢕⢱⠱⡑⡕⡱⢨⢃⢆⠣⡘⡌⠆⡂⡢⡑⠌⢌⠢⡑⡁⡊⠄⠅⠢⢘⣦⡁⡂⠐⠠⢈⠣⠐⠀⠎⡪⠰⡘⡌⡪⡪⢯⡺⣵⡳⡯⡯⣗⡯⣗⡯⡯⡳⠙⠜⣘⢸⣙⣞⡽⡺⠐⡀⡣⢱⢱⢱⡪⣹⣿⣯⣿⣿⣽⣿⡿⣟⣿⣾⡿⣿⣿⡿⣟⣯⣿⣿
⠨⡢⡑⢜⢘⠜⡸⢘⢌⠆⡕⢔⡑⡔⢕⠡⡂⡊⡢⢑⠔⢅⢃⠢⢑⠐⠔⡠⢑⠄⡃⢆⠕⡨⡘⣬⠌⡂⣳⣷⠄⠅⡘⠐⡀⠂⡁⠌⡊⢎⠔⢕⢌⢪⢳⡹⣪⢞⡽⣝⢮⣻⡺⣜⣖⢮⢏⠯⡪⣺⢺⡪⠎⠠⢐⠐⡌⡪⡢⣻⣯⣒⢿⣯⣿⣾⣿⣷⣿⣿⣿⣟⡿⣿⣷⣿⣿⣿⡿⣿
⢌⢂⠪⠨⡂⠕⢌⠢⡢⡑⢜⢐⢑⢌⠢⡑⢔⠔⢜⠰⡑⡑⠄⠕⡠⠡⠑⠄⠅⡂⡪⡂⡣⣫⢷⢹⣣⡊⠔⣿⢺⣲⣄⡡⠀⠅⠠⢂⠪⡨⡊⡪⡪⡊⡆⢝⢜⢵⢝⢮⡳⡳⣝⡞⡮⡣⡣⡣⣣⡳⡝⢼⠀⢂⠂⢅⢣⢣⢹⣽⣿⢿⣞⣿⢿⣽⣾⣯⣿⣿⣾⣿⣿⢿⣽⣿⣽⣿⣻⣿
⠔⡨⠨⡨⢂⠣⡑⡑⢔⠨⠢⡑⢔⠢⠱⡘⢔⠡⠅⢕⠨⡐⢡⢑⠠⠡⠡⠡⠨⠢⡱⡱⡽⣽⢿⡷⣝⢗⢅⠫⢫⠳⡙⡪⢀⠠⢑⢀⢂⢒⠌⢆⢣⢣⢝⠰⡐⢔⠩⡑⠹⢹⢪⢞⢽⡹⣝⣞⢞⢎⢎⢽⣷⠡⡈⢔⢕⢕⢽⣷⣿⣿⣿⣽⣿⣿⢿⣻⣿⣾⣿⣾⣿⣿⡿⣿⣽⣿⣜⣮
⢈⠢⡑⠔⡡⠊⠔⡨⠠⠡⠡⠨⢐⠨⠨⡐⡐⡡⠡⡁⡢⠨⢂⠂⢌⠌⢌⠌⣜⣼⣽⣺⡝⡾⡹⡹⡸⣝⢜⢮⡲⣕⢬⠢⡂⠆⡂⡂⠢⠀⠕⡑⡌⡪⢪⢱⢡⠣⡑⡌⡊⣂⠂⠉⠘⠊⠃⠓⣡⢇⣗⢽⡗⣕⠀⡎⡎⡦⣿⢿⣷⣿⣯⣿⣿⣾⣿⣿⡿⣷⣿⣷⣿⣷⣿⣿⡿⣯⣿⣿
⠠⡑⠌⢌⠢⠑⢅⠢⠡⠡⠡⡑⠄⠅⢅⢂⠢⠨⢂⠢⢊⠌⢄⠅⠅⢌⢂⢣⡮⣷⡿⡎⡎⡞⡜⣜⢕⢗⡽⣕⢗⡕⣗⢽⡹⡵⣢⢦⢅⠅⢌⠐⢅⠇⡇⡎⡪⡪⡊⡆⢕⠔⠀⠀⠈⠌⡨⢐⠨⢙⢎⣟⣯⠇⢌⢎⢂⢻⣽⣿⢿⣷⣿⣿⣾⣿⣯⣿⣿⢿⣯⣷⣿⣯⣿⣷⣿⣿⣿⣻
⠨⠢⡑⡡⠨⡊⠔⢌⢊⠌⢌⠔⠌⢌⢂⠢⡡⡑⡐⢅⠅⡪⢐⠡⡑⢕⢨⣾⡿⡟⢟⠕⡕⢕⠝⠜⡜⣕⠧⡓⡯⡺⡵⡫⣞⣝⢮⡳⣝⣝⢔⢅⠅⢇⢇⢇⢇⢎⢪⢪⠢⡃⠀⠀⠁⠀⠂⠢⠡⡑⡰⡐⠝⢄⠕⢌⢂⢂⢳⣿⣿⡿⣷⣿⣷⣿⣯⣿⣾⣿⣿⣿⣻⣽⣿⣽⢯⣾⣿⣿
⠨⡈⡂⡪⠨⡂⠕⡁⡂⡊⢔⢬⠮⣒⣥⢷⠻⡐⠅⢕⠨⢂⠢⡣⢑⢡⣟⣿⠘⠜⡌⣆⢮⢢⡕⣗⡬⣢⣣⡣⡧⣕⢕⣍⡪⡨⡣⡫⣞⢮⡳⡕⡅⡣⢣⢣⢣⢣⢣⠪⡒⡄⠀⠁⠀⠁⡀⠈⠈⠰⡐⢜⠨⡢⢃⢅⠪⡐⠼⣿⣷⣿⣿⣿⣾⣿⣽⣿⣻⣽⣷⣟⣿⣿⣟⣿⣿⣿⣯⣿
⢐⠰⢐⠐⢥⣶⣷⣶⣾⡾⣾⡾⡝⡫⠨⠢⡑⢌⠪⢐⢈⠢⡃⠪⣐⣵⣟⠭⣊⢎⢇⢧⢳⢱⢝⢮⡺⣕⢗⡝⣞⢮⡫⣞⢵⡻⣮⣲⡡⣓⡝⣎⢧⢑⢅⢇⢇⢇⢇⢇⢕⢜⢄⢑⠈⠀⡀⠄⠀⠄⠌⡢⢱⢡⢑⠔⡑⢌⠪⡹⣿⣽⣷⣿⣷⣿⣟⣿⡿⣟⣿⣿⢿⣽⣿⢿⣽⣾⣿⣿
⠐⠌⡂⢅⢹⣯⣷⣿⣷⣿⠟⢕⢼⢐⢑⢑⠌⡐⠨⢐⠐⢅⠊⢌⣾⣟⣧⡣⡣⡱⢹⢸⢸⢜⢮⡺⡜⣞⢼⡺⣪⢞⠮⣎⢗⢝⡞⣎⢯⡳⣝⢮⡳⡥⣱⢰⢑⢕⢕⢕⢕⢌⢆⢇⠅⢅⠀⡀⠄⠀⢁⢊⠢⡑⢅⠕⡅⢕⢱⠐⡙⣿⣿⣽⣾⣿⣟⣿⣿⣿⡿⣿⣿⢿⣿⢿⣿⣟⣿⣾
⠨⠨⢂⠅⣞⣿⣻⡽⡳⣡⣳⠫⡑⡐⡡⠂⠢⠨⡈⡂⠅⢅⢊⣾⢿⢍⢇⠇⢇⢓⢕⠇⡗⢵⢱⢕⢵⢝⡜⡜⡌⡇⡏⡎⡮⡳⡹⡪⡳⣝⢮⢧⡳⣝⢮⡳⡅⡎⡜⢜⢜⢜⢌⢆⠝⡔⡡⡀⠄⢀⠀⠑⡅⢕⡐⢅⠣⡣⡱⡈⡢⢊⠻⣟⣯⣿⣟⣿⣷⣿⡿⣿⣻⣿⣯⣯⣿⡿⣟⣿
⠨⠨⢂⢊⠝⢝⣱⣵⣾⢯⣦⢊⢐⠔⠠⠡⠡⠡⢂⢊⢌⠢⣹⡷⡹⡐⡅⢕⠅⠕⠔⡑⢌⠢⡃⢕⠸⡘⢜⠑⠅⡃⠣⡑⢌⠪⡊⡣⢫⢪⢎⡇⡧⡳⡕⣝⢮⢳⡑⡅⢇⢧⢱⢪⣪⢲⣳⢸⢨⠢⡐⡀⠘⢔⠜⢌⢊⢎⢎⢆⠊⡆⡇⡻⣿⢿⣟⣿⣽⣾⣿⣿⡿⣟⣿⣟⣿⣿⣿⣿
⢈⢪⣲⣳⣳⣿⡾⣿⣾⡟⡓⡐⡐⠌⡊⠌⢌⢊⠔⣰⠢⣱⣿⣷⡑⢌⠌⡂⠁⠄⠡⠈⠄⡁⠂⡁⠅⠨⠠⢈⢐⢀⠡⡐⡐⢔⢐⠌⡐⢐⠐⢍⢊⠇⠏⡎⡮⣣⢳⡘⡌⢎⢖⠅⢗⡯⣞⢵⡪⣊⢆⠠⠀⠂⡣⡱⡘⡌⡎⡎⣮⣔⢕⢕⢎⢿⣿⡿⣿⣻⣯⣷⣿⡿⣿⣿⣻⣷⣿⣿
⢐⢽⡿⣿⣟⣯⣿⠿⢑⢐⢐⠌⡐⡡⢂⢑⢐⢐⢌⡯⡨⣾⣿⣯⣿⣆⠁⠄⠁⠌⢈⠠⠁⢀⠂⠄⠌⢌⠌⠆⠕⠌⠪⠐⠅⠃⠆⠕⡐⡐⡈⠠⢀⠈⡈⠐⠩⢊⢇⢳⢸⠨⢪⢪⠢⡫⣞⢵⡫⣞⡔⡅⡂⠀⠐⠜⡌⡪⢪⢪⢺⣿⣳⡱⡱⡕⣕⢿⣿⣿⡿⣟⣯⣮⣫⣿⣿⣻⣽⣾
⢷⣗⣟⢿⡻⢏⠅⡑⡐⠔⡐⢌⢐⢐⢐⢐⢐⠔⡘⠅⣾⣿⣯⣿⢾⣿⡆⠀⢁⠠⢀⠠⠐⡐⢈⠌⠨⠐⠈⢈⢀⠅⡢⢒⠔⡢⡂⡂⠄⠠⠈⢈⠂⡂⡂⡡⠐⢀⠐⠡⢊⠪⡢⢑⢕⢕⢽⣕⢯⢞⢮⣣⢅⠨⡀⠀⢕⢜⢸⢸⡸⣿⡿⣟⣎⢮⡪⡪⢝⢷⣿⣿⣯⣾⣿⣿⣻⣿⣿⢿
⣿⣿⢿⡯⠃⢅⢂⢂⢊⠌⡐⡐⡐⡐⡐⡐⡐⡐⡰⣵⣹⣳⣷⡩⠛⠓⠠⠈⠄⠂⠄⠂⠡⠐⠀⠐⢀⢐⠨⢂⢑⠌⡢⢑⢌⠢⡑⠕⡅⢅⠀⢂⠠⠠⢀⠂⡁⢂⠐⠠⠀⠌⢌⠢⡑⡕⡕⠵⡯⣯⣳⡳⡳⠀⢕⠅⠄⢣⠱⡱⡱⣻⣿⣿⣽⣯⣿⣮⡪⡪⡎⡿⣿⣻⣽⣾⣿⣿⣾⣿
⣿⣾⡟⡐⡡⢁⢂⠢⠂⢅⠂⡂⡂⡂⡂⣂⢆⢢⣿⡿⣿⡿⣿⣿⡄⠈⠄⠁⠌⠀⠂⠁⠐⠈⡀⠅⢂⢐⠨⡐⡐⠅⢌⠢⠢⡑⠌⢌⠌⡢⢃⠢⠨⠨⢐⠠⠂⠄⠌⡀⠡⠐⢀⠁⠊⢜⢌⠇⡏⣞⢮⣞⡝⠀⡧⣃⢇⠌⡪⡪⡪⣙⢯⣿⣷⣿⣷⣿⣻⣮⡪⡪⡪⡝⢿⡿⣟⣷⣿⣟
⣿⣻⢂⢊⠄⢅⠂⢅⠑⠄⠅⡂⡂⡂⡢⣿⡂⣾⣟⣿⣿⢿⣟⣿⠂⡈⢀⠈⡀⢈⠀⠁⢀⠁⠠⠐⡀⠂⠌⡐⡨⠨⢂⠅⠕⡨⠨⢂⠑⠄⠡⢑⠁⠅⢂⢑⠈⡈⠢⡐⡠⢈⠠⠀⠅⡕⢌⠪⡌⡲⡙⠎⠎⢠⡻⣪⢦⢑⠈⢎⢜⢔⢽⣿⢿⣾⣿⣾⣷⣿⢿⣮⢪⢪⢪⢪⢻⢻⢿⣟
⣿⢯⠐⠄⠕⡠⠑⠄⠅⢅⠕⡐⡐⠔⣽⣿⢊⣿⣟⣿⣽⣿⣟⣷⠀⠠⠀⠠⠀⠠⠀⠐⠀⠄⠁⠄⢂⠡⠑⡐⠄⠕⡠⠡⡑⠠⠡⡑⠨⠨⠐⠠⠡⠈⠄⡐⢀⠨⠂⠢⡈⡢⠨⢂⠅⡇⢌⠪⡸⡰⡘⡔⡈⡮⡺⣝⡵⡣⡃⢅⢣⢱⢸⣿⣿⡿⣷⣿⣯⣿⣿⣿⣷⣕⠧⣇⢇⢇⢇⢏
⡿⡯⡈⠪⠨⠠⠡⠡⢡⢑⠰⡐⡌⢌⣿⡿⣸⣿⡿⣿⣟⣯⣿⣿⣿⣶⣌⡠⠐⠀⠐⠈⠀⠄⠂⠐⡀⢂⠡⢐⠈⠌⡐⠡⡂⠅⠅⠂⠅⠡⢂⠐⢀⠈⠐⠀⠄⢊⠢⣁⡐⠄⠅⠅⡢⠅⢑⠱⡈⢎⠪⡊⡎⡮⣪⣪⢺⡘⡼⣅⠪⡸⡨⢿⣷⣿⣿⣯⣿⣯⣷⣿⣯⣿⣿⣵⣯⣺⢮⣪
⣏⠢⠨⡊⠌⢌⠌⠌⡂⢆⢕⢸⣷⢁⢻⡯⣺⣿⢿⣿⢿⣿⣻⣷⣿⣷⣻⣿⣶⣌⠄⠐⠀⠂⢀⠁⠄⢂⠐⡐⠨⢐⢈⠢⠨⡘⠨⡈⠌⡈⠄⡀⠄⠀⠁⢂⠀⠀⠄⠁⡘⠸⢸⢨⠊⠄⠄⠁⢊⢪⢑⠅⡇⡗⣕⢗⣳⡹⣝⢮⢆⢊⢆⢑⠻⣯⣿⣯⣿⣟⣿⣯⣿⣟⣯⣿⣟⣿⣷⣟
⠆⢅⠕⡐⡡⠡⡈⡂⠪⡐⢴⣹⣿⣧⢂⠫⣺⣿⣿⢿⣿⢿⣟⣿⣽⣿⣻⣿⡍⠁⠀⢀⠐⠀⠠⠐⠈⠄⠂⠄⠡⢂⢐⠨⢐⠨⢐⠨⠐⡀⡂⠄⠠⠀⢈⠠⠀⠠⠐⢀⠠⠀⠀⡀⠌⠢⠡⠡⡀⢐⠱⡁⢧⢇⢯⢳⠵⣝⢮⣫⢳⡢⢊⠔⠱⡨⠻⣿⣽⣿⣟⣯⣿⣿⢿⣿⣻⣿⣯⣿
⡍⡂⡢⢂⢊⠔⡐⠌⡂⡊⢾⡮⣾⣿⣷⣌⢺⣿⣻⣿⡿⣿⣿⢿⣟⣿⣟⣿⡇⠈⠀⠠⠐⠀⠂⢀⠁⢂⠁⠌⠐⡀⠂⠌⠠⠨⢐⠨⠠⢀⠐⢈⠐⠀⡀⠐⠈⢀⠀⠢⢐⠀⠅⡀⢀⠀⠈⠨⢐⠀⡘⢌⢪⡳⣹⢪⡫⣎⢧⢳⡣⡇⡕⡌⡌⠢⠨⢌⢛⣯⣿⣿⣟⣿⣿⢿⣻⣯⣿⣿
⡒⢼⣂⠢⠡⢂⠊⠔⡐⢌⢺⣷⢹⣷⣿⣿⣅⡻⣻⣯⣿⣿⢿⣿⢿⣿⣻⡟⠀⡈⠀⠂⡀⠂⠈⢀⠠⠐⠀⠌⡀⢂⢈⠈⠨⠐⡐⠠⢁⢂⠐⡀⠌⠀⠀⠈⠠⠀⠄⠨⠂⢅⢂⠐⡐⡐⡀⠀⡂⡒⠢⠢⡡⡫⡎⣗⢝⣜⣎⢧⢳⢕⣝⠮⡪⠠⢁⠑⡔⣿⣿⣯⣿⣿⣻⣿⣿⡿⣟⣿
⢌⢽⢧⠨⢊⠔⢡⡑⡐⢄⠹⣿⣧⡻⣿⣽⣷⣝⣷⣽⡻⡿⣿⢿⣿⢿⡏⠀⠄⠀⡀⢁⠠⠀⡁⠀⠄⠐⠈⠀⠄⠠⠀⠌⡀⠂⠐⠈⠄⠂⡂⠂⢄⠀⠄⠁⠠⠀⠠⠈⠄⢅⢐⠠⠐⢐⠨⠠⠀⠕⠊⠡⡂⢇⢟⢮⡳⡕⡧⣫⢺⡸⡸⣕⢕⡕⢄⠐⢌⢻⣽⣿⣽⠻⣟⣯⣷⣿⣿⣿
⢐⠌⢿⣕⢐⠸⣔⢿⣔⠄⠅⠽⣾⣷⣝⢿⣿⣻⣞⣿⢿⣿⣾⢿⣽⣟⣿⣆⠐⠀⠠⠀⠠⠀⠔⠈⢀⠁⡈⠠⠐⠀⠂⠐⠀⠅⠨⠐⠈⠠⠠⠑⠠⠂⠄⠂⠀⠀⠄⠨⠀⢕⠐⡀⠂⠀⠁⢅⠑⠄⠂⠨⢨⢊⢗⣕⢗⡝⣎⢮⢣⡣⡯⣪⢳⡱⢅⠂⡐⠝⣿⣟⣯⡣⣿⣿⣿⡿⣟⣿
⢐⠅⠕⡻⣕⠌⣻⢷⢽⢮⡨⠂⠝⣿⣽⣮⡻⡿⣿⣻⣽⣿⣽⣿⣿⣻⣿⠝⠀⠐⠀⡈⠠⢈⠐⢈⠀⠠⠀⠂⠐⠈⠀⡁⠌⠀⠅⠌⢐⠀⢂⠈⠨⠈⡀⠀⠀⠐⠀⡂⠡⢐⠠⠀⠅⡈⢀⠂⠁⠅⠂⠌⡐⢅⢇⢗⡕⡧⡳⡱⡣⡣⡳⡱⡱⡑⢅⠂⠠⢑⠐⢝⢿⣿⣿⢿⣷⣿⣿⣿
⠐⢌⠌⡢⠙⢜⢈⢿⣻⣷⣵⡡⠑⠌⢟⣿⢿⣯⣽⡻⡿⣷⣿⣷⢿⣻⣿⠀⠄⠀⠁⡀⠠⠀⠂⡀⠂⠁⠄⠁⡈⠄⠁⢀⠀⠡⠐⠈⠠⠈⠄⢂⠀⡁⠠⠀⠀⠀⠂⠠⡁⠐⠄⠨⠐⡀⠐⠠⡱⠡⡁⠌⠄⠕⢜⠸⡘⢜⠨⢌⠪⡘⢌⢌⠢⡑⠔⠈⠀⠌⢌⢐⠕⣿⣿⢿⣟⣯⣿⣿
*/
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")

/*
⣿⣿⣟⣿⢯⣿⣺⡴⡵⡝⣞⢵⢫⡳⣕⢧⢳⢱⢣⢳⠱⡱⢱⠱⡝⡹⡘⢌⢎⠎⡪⣻⠌⢮⢻⢺⣝⢕⡏⡎⣞⡝⠔⢅⢫⢚⡜⡮⡪⡪⡯⣺⢝⣮⡳⡑⠌⠢⢂⢂⢂⠂⡂⡐⡐⢐⠐⠠⢂⢂⢂⢢⠢⢃⡂
⣿⣿⣽⣿⣻⣯⣷⣟⡷⡽⣜⢕⢏⢮⢣⢳⠱⡱⢑⠅⡓⢘⠈⠌⢜⢜⣐⢅⢪⡂⡎⡜⠨⡃⣇⢷⢱⡹⡜⡎⡢⣪⠮⣞⡮⢷⢽⡚⠯⡯⡯⣗⡯⣞⡞⡌⠨⡈⠄⢂⠂⠌⡀⢂⠈⠄⠨⠐⡐⢔⢐⢄⠝⢄⠇
⣿⣿⣿⣽⣿⣽⢾⢹⢸⢨⠢⡃⢇⢇⢃⠢⡁⠢⠐⠠⢐⢐⢨⡸⡸⣱⢃⠳⡯⣚⢽⡯⡳⡄⢣⢳⢣⢫⢺⠨⣾⣯⡫⣟⢮⢣⢏⢜⢮⢯⣫⣗⡯⣗⢯⢢⢡⢢⢨⠠⡈⢄⢂⢢⠡⡑⢌⡂⢎⠰⢂⠇⡬⣢⡣
⣿⣿⣿⡯⣟⢜⢜⢜⢜⢜⠜⡌⡆⡕⠈⠰⣐⠡⠨⡂⢅⠍⠆⠏⡊⣗⢵⡣⡝⠧⢯⢺⢺⢯⢸⢰⢣⣣⢳⣱⣿⢝⠙⡊⣍⢕⣕⢯⢏⣗⢵⣣⢯⡳⣝⠌⠌⢊⠪⡊⠎⡢⠑⠔⢅⣂⡢⢪⢘⠸⡐⠅⡟⡎⡢
⣿⣿⡿⣹⢜⡎⣇⢧⢣⡣⡇⣇⠎⡂⣕⡜⡆⠥⡑⡌⡔⡌⡪⡊⡆⡖⡱⡙⡜⡹⡰⢐⢜⣟⢮⡓⣝⢼⢕⣗⢿⢵⡡⠕⡕⡵⡪⡮⣣⢗⡽⣪⡻⡺⡸⢬⢪⡔⡤⡣⢣⢢⢌⠌⡔⡢⢂⠡⢂⠡⡈⡆⡪⢈⠔
⣿⡿⡽⡵⣫⢞⢮⢎⢗⢜⢜⢌⢌⢮⢣⢣⢣⢫⢊⢎⢌⢎⢪⠪⡚⡘⢜⢎⢎⢔⠨⡰⡕⣝⣗⣝⢮⡳⣯⡯⡗⡳⣹⣪⡪⢮⢺⢸⢪⢳⢝⢵⢹⢸⡸⣱⡑⡗⡕⡔⠄⠕⠕⡱⢕⣑⠡⡊⡊⠢⡸⡐⠌⠢⡑
⡿⡽⡽⡽⡵⣫⢯⡺⣝⠮⠱⡰⢍⢮⢪⡪⡪⡪⡪⡊⡆⡣⡕⡕⣕⢳⠡⡑⠱⣐⠨⡚⠜⡈⢾⣪⢗⡯⣗⡯⢈⠚⡎⡎⠮⢕⢕⢕⢜⢔⢕⢑⢅⢇⡞⡕⣕⢬⢹⡘⢌⠆⢕⠨⠐⡈⡪⠌⡜⠬⡒⡐⢕⠅⡎
⣿⣯⣟⡮⣯⣳⡫⡯⣞⣝⡽⣸⣺⡱⣱⢱⢕⢕⢕⢜⢜⢜⢜⢜⢔⡵⡪⡠⠑⠄⢅⢈⠂⡂⢀⠹⢵⣻⢋⠠⡂⢍⢪⠪⡍⡧⡹⡸⣐⢢⢅⣕⣕⢯⢪⢎⢮⡪⡎⣎⢦⡱⡒⠜⢔⠔⡐⡱⡐⠅⡢⡪⢨⠪⡈
⣿⣿⡿⢏⢚⢪⠯⡻⣺⣺⢽⣺⡷⣝⢮⢮⡳⣝⢵⡳⣕⢧⣳⣝⣵⡳⣍⠮⢨⠨⡂⡢⢨⠐⢔⢼⢼⢷⡵⡵⡵⡳⡱⡕⡇⡇⡇⡇⡧⣳⢝⡮⣎⡮⣳⣫⢳⡱⡱⡸⣲⠱⢨⢪⢐⢌⠤⡱⢑⡑⡅⠜⡐⠕⠨
⢇⢇⢣⢣⢱⢡⢱⡑⡅⡇⡏⡭⡍⡍⡏⡳⣛⢺⢹⢺⢝⠟⠞⡚⣺⢽⡪⡎⡐⢕⢜⢜⢔⢍⡆⡮⣌⢪⡊⡎⡎⡮⡪⡳⡹⣪⢪⡺⣜⢮⡳⣵⡳⡯⡳⡣⡳⡸⡸⡜⣮⣣⢑⠔⠨⣐⠱⡈⡎⠆⡌⢌⢂⠣⡡
⢇⢧⢳⡱⡕⣇⢧⢣⡣⡣⡣⣃⢏⢞⠮⡺⣜⢼⢱⢱⢱⢡⡣⣳⣳⣳⡽⣕⢵⢱⡪⣪⢪⡪⣎⢗⡵⡳⣝⢼⡪⡮⡪⡣⡯⢮⡳⣝⡮⠗⢯⢗⢏⢏⠮⡪⡌⡮⣪⢞⣞⢦⠱⡐⠅⡌⣊⢀⠃⠇⠪⢐⢅⢕⠠
⡏⡮⡪⣪⢺⢜⢎⢧⢫⢎⢗⢜⢼⢜⡜⣕⢕⢝⠺⢵⢳⣗⣯⣷⢿⢵⢯⡲⡑⡱⢙⢎⢗⢽⡺⣽⡺⣽⢺⣳⡻⣪⢯⡣⣏⢗⢯⢳⡹⠀⢂⢁⢇⢇⢗⢕⢝⢜⢮⡺⣼⢳⠱⡁⢇⢆⢕⢰⠑⡡⠃⠅⡒⠐⢅
⡺⡜⡮⡪⣎⢮⢺⢸⢸⢪⢎⡗⡕⡧⡫⣪⢞⢜⢜⢜⢔⢎⡪⡎⣏⢝⢵⢱⡢⣕⢌⢎⢜⢢⢣⢣⢕⢵⢹⢔⢝⢎⢕⢕⢕⢕⢕⢕⢵⢡⢦⠀⠫⡪⡪⡎⣇⢗⢗⣝⣞⡑⢅⠪⢑⢡⠡⠢⡘⢄⢃⠅⡡⢑⢔
⢼⡹⡪⣇⢧⢳⡱⡕⡧⡳⡱⣕⠵⡕⡽⣜⡜⣎⢎⢎⢮⢪⢮⢺⡪⡣⡇⡗⡝⡜⣕⢗⢮⠮⡦⣣⢇⢧⢣⡣⡳⡹⠜⢜⢸⢨⡪⣑⠵⠳⡕⣕⠀⠣⡣⡣⡣⡯⣳⠍⠄⢎⢔⠪⡂⠢⡡⣃⢣⠪⡡⠪⡘⢬⢪
⢮⡪⡳⣕⡝⡮⡺⡹⣪⡫⡫⡎⣗⢝⢎⢗⢝⢚⢎⢗⠵⠵⠵⣕⣵⡣⡇⡇⡇⣇⢧⢣⢳⢹⠪⢊⢝⢮⢧⡣⡺⡸⡸⢌⠜⢆⢂⢎⠍⢕⠵⡡⡃⢅⠨⡊⢇⠯⡣⢪⢥⠡⡑⣕⢜⢜⡰⢰⢁⡖⣎⠕⡌⡌⡢
⡗⡝⣞⢜⢮⢳⢝⣝⢼⡪⡯⣺⢸⢪⢺⢸⢸⢨⢢⢣⢣⢫⢱⢱⢲⢱⠹⡹⢺⢪⢮⢮⣣⢗⡭⣢⣪⡺⡇⡇⡣⡃⢇⠣⡃⠕⢔⢐⢜⢌⢪⠂⢇⠣⡂⡈⢆⢑⠨⢡⠕⣕⡕⡕⡭⡣⡪⠊⠜⡮⡕⠌⢆⢊⢆
⡮⡫⡎⡗⣕⢇⣗⢼⡸⡜⡎⡮⡪⡣⡳⣱⢱⡱⡱⡱⡕⣝⢎⢧⢣⢇⢇⢕⢕⢱⢹⢸⢪⠫⣓⢕⢗⢝⡜⡬⢪⢸⠰⡱⡸⡸⢊⢎⢆⠆⡕⢌⠢⡒⠅⢄⣂⢆⣎⢂⠑⠅⣃⠳⡒⣕⢘⢬⢊⠄⢍⠪⢐⠡⢃
⡮⣫⢮⡻⣜⡕⣗⢵⡹⡜⡵⡹⣚⢝⢞⠮⣗⢗⢽⣜⢮⡪⡞⣕⢇⢧⢱⢸⢰⢱⢱⡱⡱⡑⡕⢕⠡⢣⠓⠛⠚⠲⢵⢱⠜⠒⠓⠲⣐⠗⠓⠒⠓⢲⢍⠒⢒⠒⣌⠱⢕⡗⠓⣖⢸⠚⡪⡒⠚⠚⠓⠣⡀⠕⡁
⣇⢗⢵⢹⢸⢪⢎⢧⢳⢹⢕⢽⢸⡸⡸⡸⡸⣸⢪⢮⠳⡝⡾⡮⣓⠳⢝⢼⢪⠮⡮⣪⢎⢮⡪⡲⡨⡸⡀⢪⢻⠀⢸⡇⠄⡏⢵⠁⢸⡊⠈⢋⠛⡯⣄⠨⠉⡒⢮⡊⢆⡇⠄⠉⠄⠂⡅⠆⡈⠛⠙⡧⢂⢣⢐
⡪⣫⢳⡹⡪⡇⡗⣕⢵⡱⣕⣝⢼⡺⣜⢎⢮⢳⡣⡏⡎⡎⡪⢪⠪⡙⡎⡦⢕⢕⣘⢪⢪⢣⢳⢽⡸⡪⡂⢈⢉⣄⠞⡣⣀⠍⢉⣠⢎⠇⢈⠉⡉⢹⢄⠌⠋⣀⡼⡸⢨⡇⠐⣏⢩⠀⡎⡅⠈⡉⢉⢱⡕⢜⠲
⡹⡜⣎⢮⢳⢱⢝⢜⠜⡜⢝⢺⢳⢯⢮⣗⣝⢜⢮⢎⢇⢇⢇⢇⢇⢇⢇⢎⠪⡪⠢⢑⠱⠥⡱⡢⢇⡇⡎⡂⡂⠪⡢⣘⠄⠝⠰⠰⠐⢕⠅⢇⢜⢅⢅⠫⡉⡢⠢⢃⠣⢨⡂⡎⡜⡆⡑⠬⡑⡜⢔⠐⡍⡎⣜
⢞⣎⢮⡪⡮⣪⢪⡢⡣⡪⡸⡨⡪⣊⢳⢓⣗⢯⣗⣗⣭⡳⣝⣜⢮⣪⢮⡪⣪⢪⢪⢂⢏⣽⠎⣂⢢⡃⡕⢅⠢⡑⢴⢑⠄⡃⢅⢂⢅⢕⠸⣊⢂⢁⢆⢊⡢⢭⡘⢆⢍⠆⢧⢑⠔⢬⡡⠃⡎⢢⠡⠱⡂⠮⡇
⢵⣳⡳⡱⡣⠧⡧⣳⢱⡱⡕⡵⡱⢢⢑⠕⡱⡹⡰⢕⡷⣝⢮⢎⢎⡎⢎⠇⡳⡙⡪⡚⡙⢎⡪⡘⢄⢃⠌⡢⢱⠚⢳⡵⠚⢚⢶⠓⠢⣢⠓⢳⢬⠒⠃⠒⠣⣳⠚⢳⠞⠚⣶⠓⢳⠓⢊⠚⢔⡱⡨⢊⡰⡨⠨
⢗⢗⡕⢕⢕⠕⡕⣳⢹⠪⡕⡝⡼⡌⡆⡕⡱⡨⡊⡇⡇⢕⢏⢮⢣⡺⡰⢕⢲⢑⠔⡅⢊⠢⢃⢂⠢⠡⡨⡈⣲⠀⡘⠠⠐⡕⢼⠀⡂⡘⢀⢺⡇⠠⡏⣳⠁⢸⡔⠘⡀⡆⢉⠀⣟⢲⠋⢂⠮⡒⡅⡅⡪⠘⡨
⡇⢏⢞⠢⣕⢜⠜⡎⢎⡪⡪⡚⡜⡜⡜⡜⡜⡔⡕⡜⡌⠊⡌⣝⢾⡸⡱⢅⠝⣔⠱⢨⠘⠌⢢⢐⠕⡣⡑⡐⡸⣀⣰⠵⣈⣘⣽⣀⡯⢢⣠⣸⠱⣄⡩⣑⡨⢎⢣⣐⣰⢣⣀⣼⢰⢺⣉⣹⠰⢡⠪⡐⠄⠕⡆
⡊⡪⣪⢺⠰⡅⣣⠪⣸⢰⠪⡘⡌⡎⡪⢪⢺⢸⢸⢑⡕⡕⡕⡗⡕⡑⡜⠬⠨⡢⡑⡑⡅⢅⠢⠑⠌⡠⡒⠩⡂⠢⡰⢑⠡⡑⡅⢆⠪⢈⢂⠪⡐⠄⡂⡂⢌⠌⢑⠼⡰⢱⠑⢎⢇⣗⢅⢇⠊⠬⡘⠌⡌⡎⢜
⠆⢕⢕⢵⢱⢑⠢⡹⣰⢱⢱⢱⢑⡑⡅⢕⠅⡇⡅⡇⢇⢫⠪⡂⡕⢅⢢⡡⢃⠇⠌⡢⢅⠑⡌⢌⢢⠡⠨⡊⢌⢣⠸⡐⡂⡣⠣⡨⠊⢜⠆⢕⢌⠌⡢⡉⡆⡕⡀⣂⡊⡎⠎⢎⢌⢺⡨⡂⡎⠎⠄⢇⢒⢢⠣
⠩⡒⢕⢹⢘⢌⢎⢎⢎⠮⡸⡨⡲⡱⠡⡣⡑⡌⡢⡹⢨⠪⡊⢔⢑⠅⢅⢊⠔⡌⢌⠂⢅⢪⢐⢢⠢⢱⠱⡐⡐⠅⡣⠅⢆⠜⡘⡐⢩⢃⠝⡠⢪⡪⣊⠜⢅⠆⡊⡆⡢⡹⡎⡦⠑⠥⡱⡌⣂⢣⠩⡐⡘⠔⢵
⠢⢊⠌⡎⢎⢎⠎⡎⡢⢇⢕⢱⢨⠪⡱⢑⠇⢕⢲⢘⢌⠪⡨⣂⢊⠢⡑⠔⡡⡂⠕⢌⠜⡐⢌⢃⡙⢄⢂⠅⡖⢑⠰⢡⠃⢎⡐⡊⡢⠂⠇⠆⢕⢘⠆⡕⡑⡑⢅⠢⡪⡨⠝⡪⠊⠔⡰⠡⡐⠡⠁⡒⣥⢪⢵
*/

using ll = long long;
#define int long long
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second 
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll inf = 1e18;
const ll mod = 1e9+7;//998244353;

/*
⣿⣿⣿⣻⣿⣿⣿⣿⣿⣿⢿⢂⢂⢂⢂⠔⡐⡐⢔⢔⢡⠪⣛⣿⣿⣿⣿⣿⣿⣿
⣿⡯⣿⣯⣿⣯⣿⡿⣾⢝⢑⢐⢐⠔⢔⢱⢘⢌⢆⡧⣣⡣⡳⡜⡽⣾⣿⣯⣿⣷
⣽⣿⡿⣿⢽⣾⣿⡻⡋⡂⢆⢑⢜⠸⡸⡘⡜⣜⢜⢜⢜⢜⢕⢕⠱⡽⣿⣾⣿⣽
⢵⣻⣿⣯⣳⣿⣟⡯⠪⠐⠌⡂⢅⠇⡕⢕⢱⡿⡜⡸⡰⡑⢅⢇⠣⢝⡿⣯⣿⣿
⢼⣽⢻⣿⣻⣷⡷⡩⡱⢁⠣⢘⠄⢕⠜⠜⢒⢂⢇⣎⢆⢌⡄⢕⢁⡳⣫⣟⣯⣿
⠿⣽⣿⣿⣯⠧⡗⡕⢔⢐⢈⠐⢍⠢⡃⡣⡭⣽⣺⣺⡳⣜⢮⠸⣰⣮⣻⣿⣿⢿
⠪⡸⣘⢓⢕⠕⢕⠅⠕⡐⡐⢌⢈⠔⢌⢢⡫⣞⡾⡲⡪⡯⠇⢕⢼⣿⣾⣿⣻⣿
⠨⡂⠆⠕⡡⢊⠢⠨⡈⡮⡾⢜⠦⠂⡘⡰⡩⡚⡺⢝⢼⢡⢨⢺⣯⣿⣷⣿⢿⣟
⠡⡨⠨⢂⣢⠡⢊⢔⡽⡣⣋⢞⡝⢵⢲⡐⡕⡜⡄⠐⠨⡋⢔⢹⣿⡿⣷⣿⣿⣿
⠐⣼⢿⠫⡐⠌⡂⡾⢜⠜⡕⡽⡪⢏⡗⡧⣣⢣⢲⠠⡀⢜⠰⡡⠻⣿⣿⣯⣷⣿
⣸⣶⠟⡑⢄⢱⣸⣅⠅⠨⠈⠄⠌⡢⠨⢑⠑⢣⠱⡹⣪⠄⠑⢕⣯⢝⢿⣽⣻⣿
⡟⡐⡐⡐⣰⣰⣿⡍⠀⠂⠁⢌⠊⠔⡑⠄⠌⠄⡈⠪⡱⠏⣇⠕⡺⣿⣮⣛⢻⣿
⢇⢂⠢⢢⢯⣿⣿⣦⣄⠈⠐⠠⠡⢑⠠⠁⠈⠢⠨⠔⢘⢕⢵⣱⢑⢿⣿⡿⣷⣖
⢐⡐⠡⡿⣦⢿⣷⣿⠇⠀⢁⠨⠀⠅⢂⠁⠈⠀⡂⠌⢀⠎⣮⡪⡇⡆⠽⣿⣿⣿
⢘⢌⣧⠚⣿⢿⣷⣿⠂⠈⢀⠠⠐⠈⠠⠈⡀⠠⠐⢀⢁⠈⡎⠮⡺⡘⠐⠻⣾⣿
*/

const int N=2e5+5;
vector<int> adj[N];
int d[N];
const int K=18;
int to[N][K];
int tin[N],tout[N],t=0;
void pre(int u, int p) {
    tin[u]=t++;
    to[u][0]=p;
    for(auto&v:adj[u]) {
        if (v==p) continue;
        d[v]=d[u]+1;
        pre(v,u);
    }
    tout[u]=t++;
}
int c[N];
int up[N];

int jump(int u, int x) {
    forn(j,K) if ((x>>j)&1) u=to[u][j];
    return u;
}
int lca(int u, int v) {
    if (d[u]>d[v]) swap(u,v);
    v=jump(v,d[v]-d[u]);
    if (u==v) return u;
    for(int j=K-1; j>=0; --j) {
        if (to[u][j]==to[v][j]) continue;
        u=to[u][j],v=to[v][j];
    }   
    return to[u][0];
}

int m[N][K];

int get(int u, int x) {
    int ret=inf;
    forn(j,K) {
        if ((x>>j)&1) {
            ret=min(ret,m[u][j]);
            u=to[u][j];
        }
    }
    return ret;
}

vector<int> a[N];
int vis[N],cvis[N];

struct BIT {
    vector<int> t; int n;
    BIT(int n) {
        this->n=n;
        t.assign(n,0);
    }
    BIT(vector<int> a) {
        n=a.size();
        t.assign(n,0);
        forn(i,n) add(i,a[i]);
    }
    void add(int i, int x) {
        for (; i<n; i=i|(i+1)) t[i]+=x;
    }
    int sum(int r) {
        int q=0;
        for(; r>=0; r=(r&(r+1))-1) q+=t[r];
        return q;
    }
    int sum(int l, int r) {
        if (l>r) return 0;
        return sum(r)-sum(l-1);
    }    
};

int isanc(int l, int u) {
    return tin[l]<tin[u] && tout[u]<tout[l];
}

void solve() {

    int n,k; cin>>n>>k;
    forn(i,n-1) {
        int u,v; cin>>u>>v; --u, --v;
        adj[u].pb(v); adj[v].pb(u);
    }
    pre(0,0);
    for(int j=1; j<K; ++j) forn(i,n) to[i][j]=to[to[i][j-1]][j-1];

    forn(i,k) up[i]=-1;
    forn(i,n) {
        cin>>c[i]; --c[i]; 
        if (up[c[i]]==-1) up[c[i]]=i;
        up[c[i]]=lca(up[c[i]],i);
    }
    forn(i,n) m[i][0]=d[up[c[i]]];
    for(int j=1; j<K; ++j) forn(i,n) m[i][j]=min(m[i][j-1],m[to[i][j-1]][j-1]);

    forn(i,n) a[c[i]].pb(i);

    int ans=k-1;
    vector<pi> v; forn(i,k) v.pb({d[up[i]],i});
    sort(rall(v));
    BIT ft(2*n);
    for(auto&x:v) {
        int i=x.s;
        int z=n;
        int s=0;
        for(auto&x:a[i]) {
            z=min(z,get(x,d[x]-d[up[i]]+1));
            s+=ft.sum(tin[up[i]],tout[x]-1);
        }
        if (z < d[up[i]]) continue;
        if (c[up[i]]!=i) continue;
        //if (s) continue;
        queue<int> q; for(auto&x:a[i]) q.push(x);
        vector<int> rb={up[i]}; vis[up[i]]=1; cvis[i]=1;
        int top=up[i];
        while (q.size()) {
            int u=q.front(); q.pop();
            rb.pb(u);
            if (isanc(u,top)) {
                while (top!=u) {
                    top=to[top][0];
                    vis[top]=1;
                    if (!cvis[c[top]]) {
                        cvis[c[top]]=1;
                        for(auto&x:a[c[top]]) q.push(x);
                    }
                }
            }
            while (!vis[u]) {
                vis[u]=1;
                if (!cvis[c[u]]) {
                    cvis[c[u]]=1;
                    for(auto&x:a[c[u]]) q.push(x);
                }
                u=to[u][0];
            }
        }
        int cnt=0;
        for(auto&x:rb) {
            cnt+=cvis[c[x]];
            vis[x]=0;
            cvis[c[x]]=0;
            ft.add(tin[x],1);
            ft.add(tout[x],-1);
        }
        ans=min(ans,cnt-1);
        //ft.add(tin[up[i]],1);
        //ft.add(tout[up[i]],-1);
        //forn(i,n) cout<<ft.sum(tin[i],tin[i])<<' '; cout<<'\n';
    }
    cout<<ans<<'\n';

}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t=1;    
    //cin>>t;
    while (t--) solve();
    return 0;
}

Compilation message

capital_city.cpp:4:1: warning: multi-line comment [-Wcomment]
    4 | //   \ __ __  \
      | ^

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19548 KB Output is correct
2 Correct 3 ms 17500 KB Output is correct
3 Correct 3 ms 19548 KB Output is correct
4 Correct 3 ms 19548 KB Output is correct
5 Correct 2 ms 17336 KB Output is correct
6 Correct 3 ms 19548 KB Output is correct
7 Correct 2 ms 19548 KB Output is correct
8 Correct 3 ms 19548 KB Output is correct
9 Correct 2 ms 17500 KB Output is correct
10 Correct 3 ms 19344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19548 KB Output is correct
2 Correct 3 ms 17500 KB Output is correct
3 Correct 3 ms 19548 KB Output is correct
4 Correct 3 ms 19548 KB Output is correct
5 Correct 2 ms 17336 KB Output is correct
6 Correct 3 ms 19548 KB Output is correct
7 Correct 2 ms 19548 KB Output is correct
8 Correct 3 ms 19548 KB Output is correct
9 Correct 2 ms 17500 KB Output is correct
10 Correct 3 ms 19344 KB Output is correct
11 Correct 4 ms 17756 KB Output is correct
12 Correct 4 ms 19804 KB Output is correct
13 Correct 4 ms 19548 KB Output is correct
14 Correct 5 ms 17644 KB Output is correct
15 Correct 5 ms 17756 KB Output is correct
16 Correct 4 ms 17672 KB Output is correct
17 Correct 3 ms 17756 KB Output is correct
18 Correct 4 ms 17752 KB Output is correct
19 Correct 4 ms 17756 KB Output is correct
20 Correct 4 ms 19548 KB Output is correct
21 Correct 4 ms 17752 KB Output is correct
22 Correct 21 ms 19804 KB Output is correct
23 Correct 4 ms 18008 KB Output is correct
24 Correct 7 ms 17788 KB Output is correct
25 Correct 5 ms 19804 KB Output is correct
26 Correct 5 ms 17756 KB Output is correct
27 Correct 4 ms 17756 KB Output is correct
28 Correct 4 ms 19800 KB Output is correct
29 Correct 4 ms 17756 KB Output is correct
30 Correct 5 ms 19800 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3053 ms 95584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19548 KB Output is correct
2 Correct 3 ms 17500 KB Output is correct
3 Correct 3 ms 19548 KB Output is correct
4 Correct 3 ms 19548 KB Output is correct
5 Correct 2 ms 17336 KB Output is correct
6 Correct 3 ms 19548 KB Output is correct
7 Correct 2 ms 19548 KB Output is correct
8 Correct 3 ms 19548 KB Output is correct
9 Correct 2 ms 17500 KB Output is correct
10 Correct 3 ms 19344 KB Output is correct
11 Correct 4 ms 17756 KB Output is correct
12 Correct 4 ms 19804 KB Output is correct
13 Correct 4 ms 19548 KB Output is correct
14 Correct 5 ms 17644 KB Output is correct
15 Correct 5 ms 17756 KB Output is correct
16 Correct 4 ms 17672 KB Output is correct
17 Correct 3 ms 17756 KB Output is correct
18 Correct 4 ms 17752 KB Output is correct
19 Correct 4 ms 17756 KB Output is correct
20 Correct 4 ms 19548 KB Output is correct
21 Correct 4 ms 17752 KB Output is correct
22 Correct 21 ms 19804 KB Output is correct
23 Correct 4 ms 18008 KB Output is correct
24 Correct 7 ms 17788 KB Output is correct
25 Correct 5 ms 19804 KB Output is correct
26 Correct 5 ms 17756 KB Output is correct
27 Correct 4 ms 17756 KB Output is correct
28 Correct 4 ms 19800 KB Output is correct
29 Correct 4 ms 17756 KB Output is correct
30 Correct 5 ms 19800 KB Output is correct
31 Execution timed out 3053 ms 95584 KB Time limit exceeded
32 Halted 0 ms 0 KB -