oj.uz

Submission #1091030

# Submission time Handle Problem Language Result Execution time Memory
1091030 2024-09-19T14:23:23 Z hahahaha Inside information (BOI21_servers) C++17
100 / 100
 259 ms 42068 KB 
/**
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣤⡤⠤⣤⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡴⠛⠉⠀⠀⠀⠀⠈⠙⢷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⠶⣄⡀⠀⠀⠀⢠⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⡏⠀⠀⠉⠛⠶⣤⣸⡇⠀⠀⠀⠀⣀⣤⣶⣶⠒⠒⠒⠶⣬⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣤⠴⠶⣿⠀⠀⠀⠀⠀⠀⠈⠉⠉⠛⠒⠶⢿⣭⣀⡀⢻⡀⠀⠀⢠⡿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⠶⠛⠋⠁⠀⠀⢸⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠛⠷⣴⣞⠛⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡴⠞⠉⠀⠀⠀⠀⠀⠀⢰⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠛⢦⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠞⠋⠀⠀⠀⠀⢀⡤⠠⡄⠀⢰⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡞⠁⠀⠀⠀⠀⣠⠖⠋⠀⣸⠇⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⢀⡀⠀⠀⠀⠀⠀⠀⢦⡀⠀⠀⠀⠸⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡼⠋⠀⠀⠀⠀⢀⣴⠋⢀⢀⡴⠋⠀⢀⣼⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣽⠀⣼⢿⡄⠀⠀⠀⠀⣆⠀⠉⢦⡀⠀⠀⠀⠘⢧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡟⠁⠀⠀⠀⠀⣠⠟⠇⠀⠈⠉⠁⠀⣀⣾⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡟⢰⠏⠀⠻⣄⠀⠀⠀⠹⣄⣰⠟⠁⠀⠀⠀⠀⠀⢻⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⡟⠀⢀⣀⡖⠀⣰⠏⠀⠀⠀⠀⠀⢀⣼⣿⠋⠸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣧⡟⠀⠀⠀⠹⣦⠀⠀⠀⠀⠁⠀⣶⠀⠀⣴⠛⢧⠀⢻⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣠⠞⣩⡟⠀⠀⠈⠉⠀⢀⡟⠀⠀⢀⣀⣠⣤⣾⡿⠗⠒⠚⣿⠠⣤⠀⠀⠀⠀⠀⠀⠀⢸⣿⠓⠒⠲⠶⠶⠾⢷⣤⣀⣀⠀⠀⠙⣧⠀⠹⣆⣼⠃⠀⢷⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠟⢁⡼⣿⠁⠀⠀⠀⠀⠀⢸⠃⠀⠀⠈⠉⢠⡾⠋⠀⠀⠀⠀⠸⣆⠙⣧⡀⠀⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⠻⣆⠉⠁⠀⠀⢹⡄⠀⠈⠁⠀⠀⠘⣷⢦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⣠⡶⠋⢀⡴⠋⢰⡏⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⣠⠟⠀⠀⠀⠀⠀⠀⠀⢻⡄⢸⣷⣄⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠈⢳⣄⠀⠀⠸⣧⠀⠀⠀⠀⠀⠀⢿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢰⣾⡥⠴⠞⠋⠀⠀⣼⠀⠀⠀⠀⠀⠀⠀⣸⠀⠀⠀⣰⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⡄⣷⠙⠷⣄⡀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢷⣄⠀⣿⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣿⡆⠀⠀⠀⠀⠀⠀⢸⡄⠀⣼⢏⣀⣤⣶⣦⣤⣶⣶⣶⣶⣶⣿⣿⣾⡆⠀⠈⠻⢦⣼⡇⢰⣶⣶⣶⣶⣶⣶⣶⣤⣤⣤⣦⠙⢧⣿⠀⠀⠀⠀⠀⠀⢸⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⠀⠘⣇⣼⠏⠘⣿⡿⢿⣿⣿⣿⣿⣿⡏⠉⠉⠉⠙⠃⠀⠀⠀⠀⠉⠁⠘⠛⢻⣿⣿⣿⣿⣿⣟⠛⢛⠷⠀⠀⣿⠀⠀⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⡟⣷⠀⠀⠀⠀⠀⠀⠀⢻⡏⠀⠀⠀⠀⣸⣿⣿⣿⣿⣿⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⢰⡏⠀⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣷⢹⣆⠀⠀⠀⠀⠀⠀⠈⣷⠀⠀⠀⠀⢹⣿⣿⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⣾⠀⠀⠀⠀⠀⠀⢰⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢿⠘⣿⣆⠀⠀⠀⠀⠀⠐⠘⣧⠀⠀⠀⠘⢿⣿⣿⣿⣿⠏⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣿⣿⣿⡿⠃⠀⠀⠀⣼⠃⠀⠀⠀⠀⠀⣰⠟⠐⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠸⣇⣿⠙⣧⣄⠀⠀⠀⠀⠀⠘⢧⡀⠀⠀⠈⢹⠿⢟⡋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢻⡿⠀⡀⠀⠀⣼⠃⠀⠀⠀⠀⣀⡾⠋⠀⣴⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⣿⠀⣿⠝⠳⣤⣀⡀⠀⠀⠈⢷⣤⠇⢠⡞⠠⠾⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠟⠁⡾⠃⣠⡾⠃⠀⠀⣀⣤⠾⠋⠀⠀⠀⡿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⣸⣿⠀⠀⠀⠉⠙⠓⡶⠦⠤⣿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠓⢰⡿⠤⠴⠶⣿⠉⠀⠀⠀⠀⠀⢠⡇⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⢻⠀⠀⠀⠀⠀⠃⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢲⣄⠀⠀⠀⠀⠀⠀⠀⢀⣴⠆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡟⠀⠀⠀⠀⠀⠀⢸⡇⣸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⡿⢸⡇⠀⠀⠀⠀⠀⢿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠛⠲⠤⣤⠤⠴⠞⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⡏⠀⠀⠀⠀⠀⠀⢸⠇⠈⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⡇⢸⡇⠀⠀⠀⠀⠀⢸⣿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢿⡇⠀⠀⠀⠀⠀⠀⢺⢀⠀⢿⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⢷⠛⣇⠀⠀⠀⠀⠀⠈⣿⠉⠻⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣅⣸⠀⠀⠀⠀⠀⠀⢀⣿⢸⡀⢸⡇⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡿⠘⣀⣿⠀⠀⠀⠀⠀⢷⢸⡄⠀⠈⠙⠶⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⡴⠟⠁⠀⠈⣿⠀⠀⠀⠀⠀⠀⠈⡟⣼⡇⠀⣧⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⡇⠀⢿⢿⠀⠀⠀⠀⠀⠀⠈⣧⠀⠀⠀⠀⠀⠉⠛⠶⢤⣤⣀⣀⠀⣀⡀⠀⠀⠀⠀⠀⢀⣠⡴⠞⠋⠁⠀⠀⠀⠀⢀⡏⠀⠀⠀⠀⠀⠀⢠⡇⢹⣤⠀⢹⡄⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⡿⢸⡆⠀⠀⠀⠀⠀⠀⢻⡆⠀⠀⠀⠀⠀⠀⠀⠀⣿⡿⠟⠋⠉⠁⠀⠀⠀⠀⠀⢸⠁⠀⠀⠀⠀⠀⠀⠀⠀⢸⠇⠀⠀⠀⠀⠀⠀⢸⡇⠈⣟⠀⠈⣷⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢰⡟⠀⢰⡇⠘⡇⠀⠀⠀⠀⠀⠘⠀⣷⠀⠀⠀⠀⠀⠀⠀⠀⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⡿⠆⠀⠀⠀⠀⠀⠀⣼⠁⠀⢻⡀⠀⠸⣇⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣼⠁⠀⣼⠁⠀⣿⠀⠀⠀⠀⠀⠀⠀⠻⣇⣀⠀⠀⠀⠀⠀⠀⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡀⠀⠀⠀⠀⠀⠀⠀⣰⡇⠀⠀⠀⠀⠀⠀⠀⣿⡆⠀⠈⣷⡀⠀⢻⡄⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢰⡇⠀⢀⡏⠀⠀⢻⠀⠀⠀⠀⠀⠀⠀⠀⢻⣦⣄⠀⠀⠀⠀⣠⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣧⠀⠀⠀⠀⠀⣠⣾⣿⠀⠀⠀⠀⠀⠀⢠⣠⡇⡇⠀⠀⠸⣯⡀⠀⢷⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⡾⠀⠀⣼⠁⠀⠀⠸⡇⠀⠀⠀⠀⠀⠀⠀⠀⢿⣽⡧⠴⢶⣿⣿⠖⠒⠛⠛⠃⠀⠀⠀⠚⠋⠉⠉⠉⠙⠓⠲⢾⡛⠻⣽⠃⠀⠀⠀⠀⠀⠀⢸⣿⣃⠀⠀⠀⠀⢹⣷⠀⠘⣧⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣸⠃⠀⢸⡏⠀⠀⠀⢀⣿⠀⠀⠀⠀⢀⣀⠀⠈⠈⢷⠖⠚⠋⠁⢹⡇⠀⢀⣴⠶⠶⢦⣄⣀⣤⡶⠶⠤⠤⠤⠶⠾⠇⢰⡏⠀⠀⠀⠀⠀⠀⠻⣿⣿⣤⡀⠀⠀⠀⠀⢿⣀⠀⠸⣆⠀⠀⠀
⠀⠀⠀⠀⠀⢰⠏⠀⢀⡿⠀⠀⠀⣰⠟⢹⣿⡄⠀⠀⠀⠻⣄⠀⠀⠘⣷⣤⣄⣀⣈⡙⠛⢹⡷⢶⣦⣴⣾⣛⣻⢯⣴⣦⠴⠖⠃⠀⢀⡾⠀⠀⠀⠀⠀⠀⠀⢰⣿⡇⠀⠹⣆⠀⠀⠸⡞⣧⣆⠀⠹⣄⠀⠀
⠀⠀⠀⠀⢠⡟⠀⠀⡼⠁⠀⠀⣰⠏⠀⠈⣟⣧⠀⠀⠀⠀⢻⣆⠀⠀⠈⣧⡿⠀⠈⠉⠛⠛⣻⣿⡿⢿⣿⡍⠉⠀⠀⠀⠀⠀⠀⠀⡾⠁⠀⠀⠀⢀⣴⠀⠀⡾⣿⠁⠀⠀⠘⣧⠀⠀⢿⠘⣟⠀⠀⢻⡄⠀
⠀⠀⢀⣠⡟⠀⢀⡾⠃⠀⠀⣰⡏⠀⠀⠀⣻⠘⣧⠀⠀⠀⠀⢻⣷⡄⠀⠘⢷⡀⠀⠀⠀⠀⠩⣉⠁⠈⣛⡁⠀⠀⠀⠀⠀⠀⣀⣾⠁⠀⠀⣀⣠⣟⠁⠀⣠⣤⡟⠀⠀⠀⠀⠘⣧⡄⠘⡇⠙⣇⠀⠀⠻
*/
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

#define i64 long long
#define ld long double
#define bit(n,i) ((n>>i)&1)
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define FOR(i,a,b) for(int i=a; i<=b; i++)
#define FOD(i,a,b) for(int i=a; i>=b; i--)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
#define __sumairu__ signed main()
#define die_hard_onimai_fan void seggs()
#define file(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
#define brute(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".ans","w",stdout);}
#define TIME (1.0*clock()/CLOCKS_PER_SEC)
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ai(n) array<int,n>
#define dbg(x) {cerr<<#x<<' '<<x<<endl;}
#define dbgArr(arr,n) {cerr<<#arr;FOR(_i,1,n)cerr<<' '<<(arr)[_i];cerr<<endl;}

template <typename T,typename U>
ostream& operator<<(ostream &os,pair<T,U>p){
    return os<<"{"<<p.fi<<", "<<p.se<<"}";
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

i64 Rand(i64 l,i64 r)
{
    i64 ans=l+1ll*rd()*rd()%(r-l+1);
    assert(l<=ans&&ans<=r);
    return ans;
}
//const i64 base=1e9+7;
//const i64 mod=(1ll<<53)+5;

#define i64 long long
#define debug 0

const int mod=1e9+7;
//const int mod=998244353;
const int inf=1e9;
///check the limits, dummy
const int N=3e5+5;

struct Fenwick
{
    int bit[N];
    int get(int i)
    {
        int ans=0;
        for(++i;i>0;i-=i&-i)ans+=bit[i];
        return ans;
    }
    int get(int l,int r)
    {
        return get(r)-get(l-1);
    }
    void add(int i,int v)
    {
        for(++i;i<N;i+=i&-i)bit[i]+=v;
    }
}f;

vector<pii>adj[N],fromto[N];
vector<int>cnt[N];
int n,q;
int ans[N],sz[N];
bool vis[N];

int dfsz(int u,int p=0)
{
    sz[u]=1;
    for(auto&&[id,v]:adj[u])if(!vis[v]&&v!=p)sz[u]+=dfsz(v,u);
    return sz[u];
}
int centroid(int u,int S,int p=0)
{
    for(auto&&[id,v]:adj[u])if(!vis[v]&&v!=p&&sz[v]>S/2)return centroid(v,S,u);
    return u;
}

int in[N];

void upd(int u)
{
    for(auto&&[id,v]:fromto[u])if(u==v||in[v]&&in[v]<=id)ans[id]=-1;
    for(int id:cnt[u])ans[id]+=f.get(id);
}

/// take
void dfs(int u,int p,int cur)
{
    upd(u);
    for(auto&&[id,v]:adj[u])if(!vis[v]&&v!=p&&id<=cur)
    {
        dfs(v,u,id);
    }
}

/// add
void dfs2(int u,int p,int cur)
{
    in[u]=cur;
    f.add(cur,1);
    for(auto&&[id,v]:adj[u])if(!vis[v]&&v!=p&&cur<=id)
    {
        dfs2(v,u,id);
    }
}

/// remove
void dfs3(int u,int p,int cur)
{
    in[u]=0;
    f.add(cur,-1);
    for(auto&&[id,v]:adj[u])if(!vis[v]&&v!=p&&cur<=id)
    {
        dfs3(v,u,id);
    }
}

void solve(int u)
{
    u=centroid(u,dfsz(u));
    vis[u]=1;

    for(auto&&[id,v]:adj[u])if(!vis[v])
    {
        in[u]=id;

        f.add(id,1);
        dfs(v,u,id);
        f.add(id,-1);

        dfs2(v,u,id);
    }
    upd(u);
    in[u]=0;
    for(auto&&[id,v]:adj[u])if(!vis[v])dfs3(v,u,id);

    for(auto&&[id,v]:adj[u])if(!vis[v])solve(v);
}

die_hard_onimai_fan
{
    cin>>n>>q;
    FOR(i,1,n+q-1)
    {
        char o;
        cin>>o;
        if(o=='S')
        {
            int u,v;
            cin>>u>>v;
            adj[u].pb({i,v});
            adj[v].pb({i,u});
            ans[i]=-3;
        }
        else if(o=='Q')
        {
            int u,v;
            cin>>u>>v;
            fromto[v].pb({i,u});
            ans[i]=-2;
        }
        else
        {
            int x;
            cin>>x;
            cnt[x].pb(i);
        }
    }

    FOR(i,1,n)reverse(all(adj[i]));
    solve(1);

    FOR(i,1,n+q-1)if(ans[i]!=-3)
    {
        if(ans[i]>=0)cout<<ans[i]+1<<'\n';
        else cout<<(ans[i]==-1?"yes\n":"no\n");
    }
}

__sumairu__
{
    FAST
    file("");

    int tt=1;//cin>>tt;
    while(tt--)seggs();
    cerr<<"\nTime elapsed: "<<TIME<<" s.\n";
}
/**
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
C 2
C 3
C 4
C 5
C 6

4 4
S 1 2
S 1 3
S 3 4
Q 2 1
Q 2 2
Q 2 3
Q 2 4
*/

Compilation message

servers.cpp: In function 'void upd(int)':
servers.cpp:134:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  134 |     for(auto&&[id,v]:fromto[u])if(u==v||in[v]&&in[v]<=id)ans[id]=-1;
      |                                         ~~~~~^~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:61:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 | #define file(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
servers.cpp:235:5: note: in expansion of macro 'file'
  235 |     file("");
      |     ^~~~
servers.cpp:61:83: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 | #define file(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
      |                                                                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:235:5: note: in expansion of macro 'file'
  235 |     file("");
      |     ^~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25176 KB Output is correct
2 Correct 31 ms 25944 KB Output is correct
3 Correct 31 ms 25936 KB Output is correct
4 Correct 32 ms 26192 KB Output is correct
5 Correct 32 ms 25936 KB Output is correct
6 Correct 38 ms 25828 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25176 KB Output is correct
2 Correct 31 ms 25944 KB Output is correct
3 Correct 31 ms 25936 KB Output is correct
4 Correct 32 ms 26192 KB Output is correct
5 Correct 32 ms 25936 KB Output is correct
6 Correct 38 ms 25828 KB Output is correct
7 Correct 32 ms 25176 KB Output is correct
8 Correct 48 ms 25432 KB Output is correct
9 Correct 33 ms 25304 KB Output is correct
10 Correct 43 ms 25336 KB Output is correct
11 Correct 37 ms 25168 KB Output is correct
12 Correct 33 ms 25180 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25180 KB Output is correct
2 Correct 88 ms 34748 KB Output is correct
3 Correct 115 ms 34580 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25180 KB Output is correct
2 Correct 88 ms 34748 KB Output is correct
3 Correct 115 ms 34580 KB Output is correct
4 Correct 24 ms 25168 KB Output is correct
5 Correct 112 ms 34244 KB Output is correct
6 Correct 65 ms 31940 KB Output is correct
7 Correct 68 ms 32200 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25180 KB Output is correct
2 Correct 175 ms 41812 KB Output is correct
3 Correct 154 ms 41812 KB Output is correct
4 Correct 138 ms 41624 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25180 KB Output is correct
2 Correct 175 ms 41812 KB Output is correct
3 Correct 154 ms 41812 KB Output is correct
4 Correct 138 ms 41624 KB Output is correct
5 Correct 23 ms 25176 KB Output is correct
6 Correct 195 ms 41860 KB Output is correct
7 Correct 149 ms 42068 KB Output is correct
8 Correct 151 ms 41044 KB Output is correct
9 Correct 156 ms 41040 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25176 KB Output is correct
2 Correct 127 ms 35156 KB Output is correct
3 Correct 128 ms 35184 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25176 KB Output is correct
2 Correct 127 ms 35156 KB Output is correct
3 Correct 128 ms 35184 KB Output is correct
4 Correct 24 ms 25180 KB Output is correct
5 Correct 148 ms 35172 KB Output is correct
6 Correct 141 ms 35224 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 25176 KB Output is correct
2 Correct 157 ms 41876 KB Output is correct
3 Correct 149 ms 41808 KB Output is correct
4 Correct 147 ms 41616 KB Output is correct
5 Correct 24 ms 25168 KB Output is correct
6 Correct 130 ms 35156 KB Output is correct
7 Correct 125 ms 35316 KB Output is correct
8 Correct 139 ms 35664 KB Output is correct
9 Correct 175 ms 35920 KB Output is correct
10 Correct 171 ms 39064 KB Output is correct
11 Correct 199 ms 37456 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 25176 KB Output is correct
2 Correct 157 ms 41876 KB Output is correct
3 Correct 149 ms 41808 KB Output is correct
4 Correct 147 ms 41616 KB Output is correct
5 Correct 24 ms 25168 KB Output is correct
6 Correct 130 ms 35156 KB Output is correct
7 Correct 125 ms 35316 KB Output is correct
8 Correct 139 ms 35664 KB Output is correct
9 Correct 175 ms 35920 KB Output is correct
10 Correct 171 ms 39064 KB Output is correct
11 Correct 199 ms 37456 KB Output is correct
12 Correct 24 ms 25180 KB Output is correct
13 Correct 160 ms 41804 KB Output is correct
14 Correct 144 ms 42068 KB Output is correct
15 Correct 176 ms 41080 KB Output is correct
16 Correct 154 ms 41048 KB Output is correct
17 Correct 24 ms 25180 KB Output is correct
18 Correct 174 ms 35164 KB Output is correct
19 Correct 136 ms 35408 KB Output is correct
20 Correct 140 ms 35688 KB Output is correct
21 Correct 141 ms 36180 KB Output is correct
22 Correct 228 ms 37492 KB Output is correct
23 Correct 251 ms 38572 KB Output is correct
24 Correct 227 ms 38228 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25432 KB Output is correct
2 Correct 30 ms 25940 KB Output is correct
3 Correct 29 ms 25948 KB Output is correct
4 Correct 30 ms 26052 KB Output is correct
5 Correct 30 ms 25936 KB Output is correct
6 Correct 43 ms 25680 KB Output is correct
7 Correct 32 ms 25268 KB Output is correct
8 Correct 90 ms 34664 KB Output is correct
9 Correct 96 ms 34752 KB Output is correct
10 Correct 24 ms 25180 KB Output is correct
11 Correct 147 ms 41808 KB Output is correct
12 Correct 159 ms 41808 KB Output is correct
13 Correct 133 ms 41508 KB Output is correct
14 Correct 25 ms 25176 KB Output is correct
15 Correct 146 ms 35236 KB Output is correct
16 Correct 126 ms 35220 KB Output is correct
17 Correct 125 ms 35664 KB Output is correct
18 Correct 128 ms 35920 KB Output is correct
19 Correct 195 ms 38972 KB Output is correct
20 Correct 177 ms 37456 KB Output is correct
21 Correct 95 ms 35132 KB Output is correct
22 Correct 92 ms 35296 KB Output is correct
23 Correct 147 ms 35468 KB Output is correct
24 Correct 105 ms 35664 KB Output is correct
25 Correct 161 ms 38456 KB Output is correct
26 Correct 151 ms 34396 KB Output is correct
27 Correct 130 ms 34504 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25432 KB Output is correct
2 Correct 30 ms 25940 KB Output is correct
3 Correct 29 ms 25948 KB Output is correct
4 Correct 30 ms 26052 KB Output is correct
5 Correct 30 ms 25936 KB Output is correct
6 Correct 43 ms 25680 KB Output is correct
7 Correct 32 ms 25268 KB Output is correct
8 Correct 90 ms 34664 KB Output is correct
9 Correct 96 ms 34752 KB Output is correct
10 Correct 24 ms 25180 KB Output is correct
11 Correct 147 ms 41808 KB Output is correct
12 Correct 159 ms 41808 KB Output is correct
13 Correct 133 ms 41508 KB Output is correct
14 Correct 25 ms 25176 KB Output is correct
15 Correct 146 ms 35236 KB Output is correct
16 Correct 126 ms 35220 KB Output is correct
17 Correct 125 ms 35664 KB Output is correct
18 Correct 128 ms 35920 KB Output is correct
19 Correct 195 ms 38972 KB Output is correct
20 Correct 177 ms 37456 KB Output is correct
21 Correct 95 ms 35132 KB Output is correct
22 Correct 92 ms 35296 KB Output is correct
23 Correct 147 ms 35468 KB Output is correct
24 Correct 105 ms 35664 KB Output is correct
25 Correct 161 ms 38456 KB Output is correct
26 Correct 151 ms 34396 KB Output is correct
27 Correct 130 ms 34504 KB Output is correct
28 Correct 26 ms 25168 KB Output is correct
29 Correct 36 ms 25436 KB Output is correct
30 Correct 43 ms 25212 KB Output is correct
31 Correct 32 ms 25504 KB Output is correct
32 Correct 36 ms 25168 KB Output is correct
33 Correct 31 ms 25168 KB Output is correct
34 Correct 24 ms 25172 KB Output is correct
35 Correct 94 ms 34244 KB Output is correct
36 Correct 70 ms 31776 KB Output is correct
37 Correct 71 ms 31940 KB Output is correct
38 Correct 23 ms 25172 KB Output is correct
39 Correct 161 ms 41556 KB Output is correct
40 Correct 155 ms 41624 KB Output is correct
41 Correct 171 ms 40784 KB Output is correct
42 Correct 152 ms 40784 KB Output is correct
43 Correct 32 ms 25172 KB Output is correct
44 Correct 155 ms 34896 KB Output is correct
45 Correct 137 ms 34900 KB Output is correct
46 Correct 151 ms 35636 KB Output is correct
47 Correct 144 ms 35668 KB Output is correct
48 Correct 202 ms 37096 KB Output is correct
49 Correct 259 ms 38104 KB Output is correct
50 Correct 254 ms 37744 KB Output is correct
51 Correct 92 ms 33088 KB Output is correct
52 Correct 68 ms 32704 KB Output is correct
53 Correct 71 ms 32444 KB Output is correct
54 Correct 68 ms 32792 KB Output is correct
55 Correct 67 ms 32516 KB Output is correct
56 Correct 123 ms 34124 KB Output is correct
57 Correct 127 ms 35788 KB Output is correct
58 Correct 162 ms 34272 KB Output is correct
59 Correct 166 ms 33984 KB Output is correct