This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*░░░░░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░ ░░░░░░ ░░ ░░ ░░░░░░░░░░░░ ▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓██▓▓██████████████▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▒▒▒▒░░▒▒
▒▒░░░░░░░░░░░░░░▒▒░░░░░░░░ ░░ ░░░░░░ ▒▒░░░░░░░░ ▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓████████████████████████▓▓██▓▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓░░░░▓▓▓▓▒▒▒▒
░░░░▒▒▒▒░░░░░░░░░░░░░░░░ ░░ ░░ ▒▒▒▒░░░░ ░░▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓██████████████████████████████████▓▓▓▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▓▓▒▒▓▓▓▓▒▒░░▒▒▓▓▓▓▒▒
░░░░░░░░░░░░▒▒░░░░░░░░░░░░░░░░░░ ░░ ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓██████████████████▓▓████████████████▓▓▓▓▓▓▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▓▓▓▓
▒▒░░░░░░░░ ░░░░░░░░░░░░ ░░░░░░░░░░░░░░ ░░ ░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▓▓██▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓████████████████████████████████████████████████▓▓▓▓▓▓▒▒▓▓▓▓▒▒▒▒▓▓▓▓▓▓▓▓▒▒▒▒▒▒▓▓▓▓▒▒▓▓▓▓▒▒▒▒
░░▒▒░░░░ ░░ ░░░░ ░░░░░░░░░░░░░░░░░░ ░░░░ ▓▓▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓██████████▓▓▓▓██████████████████████████████████████████████▓▓▓▓▓▓▓▓▓▓▒▒▓▓▓▓▒▒▓▓▓▓▒▒▒▒▒▒▓▓▓▓▒▒▓▓▓▓▓▓▓▓
░░░░ ░░ ░░░░░░░░░░░░░░░░░░ ░░░░ ░░ ░░ ▓▓▓▓▒▒▒▒▓▓▓▓▓▓▓▓▓▓████████████████████████████████████████████▓▓██████████████████████████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▒▒░░ ░░ ░░░░ ░░░░░░░░░░ ░░░░░░░░ ░░░░▒▒░░ ▒▒██▓▓▓▓▓▓████▓▓██████████████████████████▓▓██████████▓▓████▓▓▓▓████████▓▓██████████████████████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
░░░░░░░░ ░░ ░░░░░░░░░░░░ ░░ ▒▒▓▓██████████████████████████████████████████████▒▒▒▒██▓▓▓▓████████▒▒▓▓████████████████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
░░░░░░░░░░░░░░░░░░ ░░ ░░░░░░░░▒▒░░░░░░░░░░░░ ▒▒██▓▓██▓▓██████▓▓██████████████████████████▒▒▓▓██▓▓▓▓▓▓██▓▓████████▓▓▓▓████████████████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
░░░░░░░░░░░░░░░░ ░░ ░░░░░░░░░░░░░░░░▒▒▒▒░░░░░░▒▒▒▒▒▒░░░░▒▒▒▒▓▓▓▓▓▓▓▓▓▓████████████████████████▒▒▒▒██▓▓▒▒░░██████████████▒▒▒▒░░████████████████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
░░░░░░ ░░░░░░ ░░ ░░░░░░░░▒▒▒▒▒▒▒▒░░░░░░▒▒▒▒▒▒░░░░░░▓▓▓▓▓▓▓▓▓▓██████████████████████████▒▒▒▒░░▓▓▒▒░░▓▓██████████▓▓▒▒▒▒░░░░████████████████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
░░▒▒░░ ░░░░ ░░▒▒▒▒░░░░░░▒▒░░░░░░ ▒▒▓▓▒▒▒▒▓▓▓▓████████████████████████▓▓▓▓▒▒░░░░▓▓░░░░▓▓████████▒▒▒▒░░░░░░░░██████▓▓████████████▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
░░ ░░ ░░░░░░░░░░░░ ░░▒▒▒▒░░░░░░░░▒▒░░░░▒▒▓▓▓▓██████████████████████████████▒▒░░▒▒▒▒░░░░░░░░░░██▓▓██▒▒▒▒░░░░░░░░░░▒▒▓▓██▒▒▓▓██████▓▓████▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▒▒▒▒▒▒▒▒░░ ░░ ░░░░░░░░▒▒░░░░░░░░░░░░▒▒░░░░ ░░░░██████████████████████████████████▓▓▒▒░░▒▒░░░░░░░░░░░░██░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒██████▓▓████████▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▒▒▒▒░░ ░░░░░░░░ ░░░░░░░░░░░░░░░░▒▒░░ ░░░░░░░░░░░░▓▓██████████████████████████████████▒▒░░░░▓▓▓▓▒▒▒▒▓▓░░░░▒▒░░░░░░░░░░░░░░░░▒▒▓▓██▒▒░░░░▓▓████▓▓██████████▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓
██░░░░░░ ░░░░░░ ░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒████▓▓▓▓▓▓▓▓▓▓████████████████████▓▓░░░░██░░░░░░░░░░▓▓░░░░░░░░░░░░░░░░▓▓▒▒░░░░░░▒▒▓▓░░░░████▓▓██████████████▓▓▓▓▓▓▓▓▓▓▒▒▒▒▓▓▒▒▒▒▓▓▓▓
▒▒▒▒▒▒▒▒▒▒░░░░ ░░░░░░░░░░░░▓▓▒▒▒▒░░▒▒░░░░░░░░░░░░░░░░▒▒▓▓▓▓▒▒▒▒░░░░▓▓████████████████████▒▒░░▓▓░░ ░░▓▓░░░░░░░░░░░░▒▒░░ ░░░░██░░██████████████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒
░░░░ ░░░░░░░░ ░░░░░░▒▒▓▓▒▒▒▒▒▒░░▒▒▒▒░░ ░░░░░░░░░░░░▒▒▒▒▒▒▒▒░░▒▒▓▓██████████████████████░░░░▓▓░░ ░░ ▒▒░░░░░░░░░░░░░░ ░░▒▒░░██████████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒
░░░░▒▒░░░░ ░░ ░░░░░░▒▒▒▒▒▒▓▓▓▓▓▓▒▒░░░░░░░░░░▒▒░░▒▒▒▒░░░░░░▒▒▒▒▓▓▓▓██████████████████████████░░▒▒░░ ▒▒▒▒ ░░░░░░░░░░░░░░ ░░░░██ ░░▓▓████████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓██▓▓▓▓▒▒
░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒░░░░▓▓▒▒▒▒░░░░ ░░ ░░░░░░▒▒░░░░░░▒▒▓▓▓▓▓▓████████████████▓▓████████░░▓▓ ░░██ ░░░░░░░░░░░░ ▒▒██░░ ░░██████████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒
░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░▒▒▒▒▓▓░░░░▒▒▒▒▒▒░░▒▒▒▒▒▒░░░░░░░░▓▓▓▓▒▒▓▓██████████████▒▒████████▓▓▓▓ ░░▓▓ ░░░░░░░░░░░░ ▒▒▓▓ ░░██▒▒██▓▓████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓▓▓
░░░░▒▒░░░░▒▒░░░░▒▒▒▒░░░░░░░░░░░░░░░░░░▓▓▓▓▒▒▒▒▒▒░░░░░░░░▒▒▒▒░░░░░░▒▒▓▓▓▓▒▒▓▓░░▓▓████▓▓▓▓██░░▓▓██████░░▒▒░░ ░░ ░░░░░░░░░░░░ ▒▒░░ ░░██▒▒██████░░████▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓▒▒░░
░░ ░░ ░░░░▒▒▒▒░░▒▒▒▒░░░░▒▒▒▒▒▒▒▒▓▓▓▓▓▓░░░░▒▒░░░░░░░░░░▒▒░░░░▒▒▒▒▓▓▒▒░░░░░░▒▒▓▓▒▒▓▓████░░░░▒▒████░░░░▒▒ ░░░░░░░░░░░░░░ ▒▒░░██████░░██████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▓▓░░
░░░░░░░░░░░░░░▒▒▒▒░░▒▒░░▒▒░░▒▒▒▒▒▒▓▓▓▓▓▓░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░▒▒░░░░░░░░░░▒▒▒▒▓▓▓▓██████░░░░▒▒░░▒▒▒▒░░▒▒ ░░░░░░░░░░░░░░ ░░░░░░████▓▓░░██████████▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒░░▓▓▓▓░░
▒▒░░ ░░░░▒▒░░░░░░░░▒▒▒▒▒▒░░░░░░▒▒▓▓▓▓▓▓▓▓▒▒░░▒▒░░▒▒░░░░░░▒▒▒▒░░░░░░░░ ░░░░ ▒▒▒▒██████████░░░░▒▒▒▒░░░░░░░░░░░░ ░░░░░░░░░░░░▒▒░░░░░░ ▒▒░░▒▒▓▓▒▒▒▒░░██████▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░▒▒▒▒░░▒▒░░
░░░░▒▒░░▒▒░░░░░░▒▒▒▒▒▒▒▒▓▓▒▒▒▒▓▓░░▓▓▓▓▒▒▓▓▒▒░░░░░░▒▒░░░░░░▒▒▒▒▒▒░░░░ ░░ ░░██▒▒░░░░████░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░░░▒▒▓▓▒▒░░▒▒████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░▒▒▒▒░░░░
░░░░░░ ░░▒▒ ░░░░░░░░░░░░▓▓▓▓▒▒▒▒░░░░▒▒▒▒▓▓░░░░▒▒▒▒░░░░░░▒▒▒▒▒▒░░ ░░ ░░▒▒░░░░░░████▓▓░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒░░██▓▓▓▓▓▓▓▓▓▓▒▒▒▒░░▓▓▒▒░░▒▒▒▒░░░░░░░░
░░ ░░░░▒▒▒▒░░░░▒▒░░▒▒▒▒▒▒▒▒▒▒▒▒▓▓▓▓░░░░░░ ░░░░▒▒▒▒░░░░░░ ░░░░░░░░▒▒████▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░▒▒██▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓▒▒░░▒▒░░░░░░░░░░░░
░░ ░░░░░░ ░░░░▒▒▒▒▒▒░░░░▒▒░░▒▒▒▒░░▓▓▓▓░░░░░░░░░░▒▒▒▒▒▒▒▒░░░░░░░░░░ ░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒████▓▓▓▓▒▒▒▒░░▒▒░░▒▒▒▒▒▒░░░░ ░░░░░░░░
░░░░ ░░ ░░▒▒▒▒░░▒▒▒▒░░░░░░▒▒░░░░░░▒▒░░░░▓▓▒▒░░░░▒▒░░▒▒░░▒▒▒▒▒▒░░░░ ░░▒▒ ░░░░░░▒▒░░░░░░░░░░░░▓▓ ░░░░░░░░░░░░░░░░░░░░░░░░▒▒ ░░▒▒▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒░░░░░░ ░░ ░░
░░▒▒░░ ░░░░ ░░░░░░▒▒▒▒░░░░▒▒░░░░░░░░░░░░▒▒░░▓▓▓▓░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒░░ ░░░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░▓▓▓▓░░░░░░░░░░░░░░▓▓░░ ░░ ▒▒▒▒░░▒▒▒▒▓▓▓▓▓▓▓▓▓▓▒▒░░░░░░
▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒░░░░░░░░░░░░▓▓▒▒▓▓▓▓░░▒▒░░░░▒▒░░░░░░░░▒▒░░░░ ░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▓▓░░░░░░░░░░░░ ░░ ░░▒▒▒▒▒▒░░▒▒░░░░▒▒▒▒▓▓▒▒░░░░░░ ░░
░░ ░░░░▒▒▒▒▒▒░░░░░░░░░░░░▒▒▒▒▒▒░░▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓░░▒▒░░░░ ░░ ░░▒▒▒▒▒▒░░░░ ░░░░░░░░░░░░░░ ░░░░░░ ░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓░░░░░░░░░░░░▒▒ ▓▓▒▒▒▒░░░░░░░░░░░░░░░░░░ ░░░░░░░░
░░░░░░▒▒▒▒▒▒░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▓▓▒▒▓▓▒▒▒▒▒▒▓▓▓▓▓▓▒▒▒▒░░ ░░ ░░ ░░░░░░░░░░░░░░▒▒░░▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░▒▒░░ ░░ ░░░░▓▓▓▓▓▓▓▓▓▓░░░░░░░░░░ ░░░░ ░░
░░░░░░░░░░░░░░░░▒▒▒▒░░░░▒▒▒▒░░░░░░▒▒▒▒▒▒░░░░░░▒▒▓▓▓▓░░░░░░░░░░ ░░░░░░░░▒▒░░░░░░▒▒▒▒▒▒░░▒▒░░░░░░░░░░░░░░░░ ▒▒░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░▒▒▒▒░░░░ ░░▒▒▓▓▓▓▓▓▒▒▒▒▒▒▒▒░░░░░░░░ ░░
▒▒░░ ░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░▒▒▓▓▓▓▓▓▒▒░░▒▒▒▒░░░░▒▒▒▒░░░░░░░░▒▒▓▓▓▓▓▓▓▓▓▓▒▒░░░░░░░░░░░░▒▒░░░░ ▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░▒▒▒▒░░░░ ▒▒░░░░░░▒▒░░▒▒░░░░░░░░░░░░ ░░░░░░
░░ ░░░░▒▒░░░░░░▒▒▒▒▒▒░░▒▒▒▒▒▒░░░░░░░░░░▒▒▒▒▒▒▒▒░░▓▓▓▓▓▓▒▒░░░░▒▒░░░░░░░░░░░░▒▒▒▒▓▓▒▒░░░░▒▒▒▒▒▒▒▒░░ ░░░░ ░░▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒░░ ░░▓▓▓▓▓▓▒▒▒▒░░░░░░░░▒▒░░ ░░░░░░ ░░░░
░░ ░░▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░▒▒░░░░░░▒▒▒▒░░░░░░░░░░░░▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░▒▒░░░░░░░░░░░░░░▒▒▒▒░░░░▒▒▒▒░░░░ ▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░▒▒▒▒▒▒░░░░░░░░▒▒▒▒░░ ░░▓▓██▓▓░░░░░░░░▒▒░░░░░░░░░░░░ ░░░░
░░░░░░░░░░░░▒▒▒▒▒▒▒▒▓▓▓▓▒▒▒▒░░░░░░▒▒▒▒▒▒░░░░░░░░▒▒▒▒▒▒▓▓▒▒▓▓▒▒▒▒▓▓░░░░░░░░▒▒▓▓▒▒░░▒▒░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒░░░░░░▒▒▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░▒▒▒▒░░ ░░░░ ▓▓▒▒▓▓▒▒▒▒░░░░▒▒░░░░░░░░░░░░ ░░
░░▒▒░░░░▒▒▓▓▓▓▒▒░░░░▒▒▒▒▒▒░░░░░░▒▒▒▒░░░░░░░░▒▒▒▒░░░░░░▓▓▒▒▓▓▒▒▒▒▓▓░░░░░░▒▒▒▒▒▒▒▒░░▒▒░░▒▒▒▒▒▒▒▒░░░░░░░░░░▒▒▓▓████████████▓▓▒▒▒▒▒▒▒▒▒▒▒▒▓▓████▓▓▒▒░░▒▒▒▒░░ ▒▒▒▒▒▒▒▒▒▒▒▒▓▓▒▒▒▒▒▒▒▒░░░░░░░░░░░░▒▒
░░▒▒▒▒▓▓▒▒▓▓▒▒▒▒▒▒▒▒▓▓▒▒░░░░░░▒▒░░░░░░░░░░▒▒▒▒▒▒▒▒░░▒▒▓▓▓▓▒▒▒▒▓▓▒▒░░░░▒▒▓▓▓▓▓▓▓▓░░▒▒▒▒░░▒▒▒▒▒▒░░░░░░░░░░▓▓▓▓██████████████▒▒▒▒▒▒▒▒▒▒▒▒████████▓▓▓▓▒▒▒▒░░ ▓▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓░░░░░░░░░░░░░░░░
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░░░▒▒░░░░░░░░░░░░░░▒▒░░▒▒░░▒▒▒▒░░░░▒▒▓▓▓▓▒▒▒▒▓▓▒▒▒▒▓▓▓▓▒▒░░░░▒▒▒▒▒▒░░░░▒▒▒▒▒▒░░░░░░░░░░▓▓██████████████▓▓▒▒▒▒▒▒▒▒▒▒▒▒██████████▓▓▓▓▒▒░░ ▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▓▓░░▒▒░░░░░░░░░░░░
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒░░░░ ░░▒▒░░░░▒▒▒▒▒▒░░░░▒▒░░▒▒▒▒▓▓▓▓▒▒▒▒▓▓▒▒▓▓▓▓▒▒▒▒░░▒▒░░░░░░░░░░░░▒▒░░░░ ░░░░▒▒▓▓████████████████░░░░░░░░░░▒▒████████▓▓▓▓▒▒▒▒░░ ▓▓▓▓▓▓▓▓▒▒░░░░▒▒░░▒▒▒▒▒▒▒▒░░░░░░▒▒░░
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓▓▓▓▓░░░░░░ ░░▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░▓▓▓▓▒▒▓▓▓▓▓▓▓▓▒▒▒▒░░░░░░░░░░░░░░░░░░░░▒▒░░░░ ░░░░██████████████████░░░░░░░░░░▓▓████████▓▓▓▓▒▒▒▒░░ ░░▓▓▓▓████▓▓▒▒▒▒░░░░░░░░░░ ░░▒▒░░░░░░
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░░░░░░░░░░░▒▒▒▒▓▓▒▒░░░░░░░░░░░░░░▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒░░░░░░░░░░░░░░▒▒▒▒░░▒▒░░░░░░░░░░░░▓▓████████████████░░░░░░░░░░████████▓▓▓▓▓▓▒▒▒▒░░░░░░░░░░░░▓▓▓▓▓▓▓▓▓▓░░░░░░░░▒▒▒▒ ░░░░░░░░░░░░
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░▒▒▒▒▒▒▓▓▓▓▒▒▒▒░░░░░░░░░░░░▒▒░░▓▓▓▓▓▓▓▓▓▓▒▒▒▒░░░░▓▓░░░░░░░░▒▒░░░░▒▒▒▒▒▒▒▒░░▒▒▒▒░░▓▓████████████████▓▓░░░░░░░░████████▓▓▓▓▒▒▒▒▒▒░░ ░░░░░░░░▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▓▓▓▓▓▓▓▓▒▒▓▓▒▒░░▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒░░▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░░░▒▒░░░░▒▒▒▒░░▒▒██████████████████▓▓░░▒▒░░▒▒██████▓▓▓▓▓▓▒▒▓▓▒▒░░ ░░░░░░░░▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░░▒▒▒▒░░░░░░░░░░░░
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓▒▒░░▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░▒▒▓▓▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░░░▒▒░░░░░░▒▒░░▓▓████████████████████████████████▓▓▓▓▓▓▓▓██▒▒▒▒░░ ░░▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒░░░░░░░░ ░░
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓▓▓▓▓▓▓▒▒▓▓▓▓██▓▓▓▓▓▓░░░░▒▒░░░░░░▒▒▒▒▒▒████████████████████████████████████▓▓████░░▒▒░░▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░░ ░░ ░░
▓▓▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░▒▒▓▓██████▓▓▓▓▒▒░░░░▒▒░░░░░░▒▒░░▓▓██████████████████▓▓▓▓▓▓████▓▓▓▓▓▓██████▒▒░░░░░░░░░░▒▒░░▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░░░░ ░░░░░░░░
▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░▒▒▓▓▓▓████████▓▓▓▓░░░░▒▒░░░░░░░░▒▒▒▒██████████████████▓▓▓▓▒▒▓▓▓▓████████████▒▒░░▒▒░░░░░░░░░░▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░ ░░░░░░░░▒▒░░░░
▓▓▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░░░░▓▓▓▓██████████▓▓▒▒░░░░░░░░░░░░▒▒░░▓▓██████████▓▓▓▓▓▓▓▓▓▓▒▒████████████████▓▓░░▒▒░░░░░░░░▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░░░░░░▒▒░░░░░░▒▒
▓▓▓▓▓▓▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░░░▒▒▓▓████████████▓▓▓▓░░░░▒▒░░░░░░░░░░▓▓██████████████████▓▓██████████▓▓▓▓▓▓▓▓▓▓░░░░░░░░░░░░▒▒░░██▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░▓▓▒▒▒▒░░░░░░
▓▓▓▓▓▓▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓░░░░░░▓▓▓▓██████████████▓▓▒▒░░▒▒░░░░░░░░▒▒▒▒████████████████████████████████████████▒▒░░▒▒░░░░░░░░░░▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░*/
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 5e5 + 5;
vector<int> l, g[maxn];
void dfs(int u, int p = -1)
{
if (g[u].size() == 1) l.push_back(u);
for (int v : g[u]) if (v != p)
dfs(v, u);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 0, a, b; i < n - 1; i++)
cin >> a >> b, g[a].push_back(b), g[b].push_back(a);
int root = -1;
for (int i = 1; i <= n; i++) if (g[i].size() > 1)
{
root = i;
break;
}
dfs(root);
cout << (l.size() + 1) / 2 << "\n";
for (int i = 0; i < l.size() / 2; i++)
cout << l[i] << " " << l[l.size() / 2 + i] << "\n";
if (l.size() & 1)
cout << l[0] << " " << l.back() << "\n";
return 0;
}
Compilation message (stderr)
net.cpp: In function 'int main()':
net.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i = 0; i < l.size() / 2; i++)
| ~~^~~~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
