fork download
copy 
  1. ///████▓▓▓▓▓▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
  2. ///████▓▓▓▓▓▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░▒▒▓▓▓▓▓▒░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓██▓
  3. ///███▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░▒▒▓▓██▓▓▒▒▓▓▓░░░░░░░░▒▓▓▓▓▓▓▓▓▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
  4. ///██▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▓▓▒▓▓██▓▓▒▓▓▓▓███▒░░░░░░░░▒▓▓▓▓▓▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
  5. ///█▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓▓▓▓█▓▒▒▓▓▓▓██████░░░░░░░░░▒▓▓▓▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
  6. ///▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▓██▓▓▓█▓▒▓▓▓█████████▓░░░░░░░░░▒▒▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▓
  7. ///▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▓█▓▓▓▓▓▓▒▓█████████████▒░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  8. ///▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▓█▓▓▓▓▓▒▒▒▓██████████████░░▒▒░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▒▓▓▒▒▒▒▒▒▒▒▒
  9. ///▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▓▓██▓▒▒▒▒▒▒▓█████████████▒░░░▒░░░▒░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▓▒▒▒▒▒▒▒▒▒
  10. ///▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▓▓██▓▒▒░░▒▒▒▒▓████████████▒▒░▒░░░░░▒░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▒▒▒▒▒▒▒
  11. ///▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒████▒▒░░░░░▒▒▓▓███████████▓░░▒▒▒░░░▒░░░░░▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒
  12. ///▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▒▒▒▓███▓▒░░░░░░░▒▒▓████████████░░░▒▒░░░▒▒░░░░░▒▒▓▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒
  13. ///▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▒▒▒▒▒▒▓███▒▒░░░░░░░▒▒▓████████████▒▒░░▒░░░▒░░░░░░░▒▒▒▓▓▓▓▓▓▒▒▓▓▓▓▓▓▓▒▒▒▒▒▒
  14. ///▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓███▓▒▒▒░░░░░▒░░▒▓█▓█████████▓░░░░░░░▒▒░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▓▓▒▒▒▒▒▒▒▒▒
  15. ///▓▓▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▒███▓▓▓▒░░░░░░░▒▓▓▓█▓█████████░▒░░░░░▒▒▒▒░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  16. ///▒▒▒▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▒▓███▓▒▓▓░░░░▒░▒▒▒▓▓█▓█████████▓░░░▒▒▒░▒▒▒░░░░░░░▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▒▒▓▓▓
  17. ///▒▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▓▓▒▒▒▒▒▒▒▓▓▓▓▒▓█▓▓▒░░░░░░▒▒▒░░░░▒▓▓▓█████████░▒░▒▒▒░▒▒░░░░░░░░░▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
  18. ///▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▓▓▓▓▓▒▒▓▓▓▓▓▓▒██▓▒▒░░░░░░▒▒▒░░░░▒▒▓▓█████████▒▒░▒▒▒▒▒▒▒░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
  19. ///▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▒▒██▓▒░░░░░░░▒▒▒▒░░░░▒▒▓█████████▓░░▒▒▒▒▒▒▒░▒░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  20. ///▓▓▓▓▓▒▒▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▒▒▒░░░▒█▓░░░░░░░░▒▒▒▒░░░░▒▒▒██████████░░▒▒▒▒▒▒░░▒░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  21. ///▓▓▓▓▓▒▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▒▒░░░░░░▒▒▓██▒░░░░░░░░▒▒░░░░░▒▒▒▓█████████░▒▒▒▒▒░░░▒▒▒░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  22. ///▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▓▓▓▒░▒▒▒▒▒▒▒▒▒▓▓███░░░░░░░░▒░░░░░▒▒▒▒▓████████▒▒▒▒▒▒░░▒▒▒▒▒░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  23. ///▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▓▒░▒▒▒▒▒▒▓▓▓▓▒▒▓▓██▓░░░▒▒░░▒▒▒░░░▒▒▒▓▓███████▓░▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  24. ///▒▒▒▒▓▓▓▒▒▒▒▒▒▒▒▒▒░░▒▓▒▒▒▒▒▓▓▓▓▓▓▓▓██▓░░▒▓▓▒▒▒▒▒░░░░▒▒▓██████▒░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  25. ///▒▒▒▒▒▓▓▒▒▒▒▒▒▒▒▒▒░░░▒▒▒▒░▒▒▓▒▒▒▓▓▓▓██▓░░░░░░░░░░░░░░░░░░░░▒░▒▒▒▒▒▒▓▓▒▒▒▓▒▒▒▒░▒▒░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  26. ///▒▒▒▒▒▓▓▓▓▒▒▒▒▒▒▒▒▒░░░▒▒▒▒▒▒▒▒▓▒▓▓▓▓█▓░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▓▒▒░▒▒░▒▒▒▒▒░▒▒░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  27. ///▒▒▒▒▓▓▓▓▓▒▒▒▒▒▒▒▒▓░░░░▒▓▒▒▒▒▒▓▓▓▓▓▓▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒░░░▒▒▒▒▓▒▒▒▓█▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  28. ///▒▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒▒▒▒░░░░▒▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒░░░▓████████▓▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  29. ///▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒░░░░▒████████▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  30. ///▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒░░░░▒███████▓▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  31. ///░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░▓██████▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  32. ///░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▓██████▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  33. ///▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░▒▓███▓█▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  34. ///▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░▒▒▒▒▒░▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒░░░░░░░░░▒▓▓█▓▓▓▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  35. ///▒░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░▒░░░░░░▒▒▒▒▒░▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒░░░░░░░░░░▒▓█▓▓▓█▓▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  36. ///▒░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░▒▒▒▒░▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒░░░░░░░░░░░░▒▓▓▓█▓█▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒
  37. ///▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░▒▒▒▒▒░▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▓▓██▓█▓▒░░░▒▒▒▒▒▒▒▒▒
  38. ///▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▓███▓█▓▒▒▒▒▒▒▒▒▒▒▒▒▒
  39. ///▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▓▓████▓▓█▓▒▒▒▒▒▒▒▒▒▒▒▒
  40. ///▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▓▓▓▓██████▓▓▓▓▒▒▒▒▒▒▒▒▒▒▒
  41. ///▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▓███████▓▓▓▓▓▒▒▒▒▒▒▒▓▓▒
  42. ///▒▒▒▒░░░░░░░░░░▒▒░▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░▒▒▓▒▒▒▓████████▓▓██▓▓▓▒▒▒▒▓▓▒▒
  43. ///▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░▒▓▒▒▒▒█████████▓▒▒▓█▓▓▒▒▒▒▒▒▒▒
  44. ///▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▓████████▓▒▒▒▒▓▓▓▓▒▒▒▒▒▒▒
  45. ///▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░▒▒▒▓▒▒░░░░░░░░░░░░░░░░░░░░░░░▒▓▒▒▒▒███████▓▒▒░░░░▓█▓▓▒▒▒▒▒▒
  46. ///▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░▒▒▒▒▓██▒░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒███████▒▒▒░░░░▒▒█▓▓▓▒▒▒▒
  47. ///▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░▒▒▒▒▒▒███▓░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒██████▒░▒░░░▒▒▒▓▓▓▓▒▒▓▒
  48. ///▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░▒▒▒▒▒▒▓▓███▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▓████▒▒▒░░░░▒▒▓███▓▓▓▒
  49. ///▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▓▓▓█▓██░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒░░░░░░▒▒███▓▒▒░░░▒▓▓███▓▓▓▓
  50. ///▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓█▓████░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░░░░░░▓██▓▓▒▒▒▒▒█████▓▒▒
  51. ///▒▒▒▒▒▒▒▒▒▒▒░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▓▓▓▓█▒███░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒░░▒▒▓██▓▓▒▒▒▓████▓▓▓
  52. ///▒▒▒▒▒▒▒▒▒░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▓▒▒▓▓▓█▓███▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒░▒▒▒▒▒▒▓██▓▒▓█████▓▓
  53. ///▒▒▒▒▒▒▒▒░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▓▓▒▒▒▒▒▓▓█████▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒░▓████▓▓
  54. ///▒▒▒▒▒▒░░░░░░░░▒▒▒▒▒▒▒▒▒▓▓▓▓▒▒▒▒▒▒▒▒▒▒▓▓█████▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▓█████
  55. ///▒▒▒▒▒░░░░░░░▒▒▒▒▒▒▒▒▒▓▓▓▓▒▒▒▒▒▒▒▒▒▒▒▓▓██████▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒██▓██
  56.  
  57. #include <bits/stdc++.h>
  58. using namespace std;
  59.  
  60. #define Task "Test"
  61. #define int long long
  62. #define el '\n'
  63. #define cnt_bit_1 __builtin_popcountll
  64. #define float double
  65. #define IO freopen(Task".inp","r",stdin); freopen(Task".out","w",stdout);
  66. #define pii pair<int,int>
  67. #define fi first
  68. #define se second
  69. #define pb push_back
  70.  
  71. const int M=2500005;
  72. const int N=3e5+5;
  73. const int INF=1e18;
  74. const int MOD=1e9+7;
  75.  
  76. int n , q;
  77.  
  78. struct Query {
  79.     int type , x , y;
  80. } qr[N];
  81.  
  82. int c[N] , dist[N];
  83. vector<int> ke[N];
  84.  
  85. void bfs(int st)
  86. {
  87.     memset(dist , -1 , sizeof(dist));
  88.     queue<int> qu;
  89.     qu.push(st);
  90.     dist[st] = 0;
  91.  
  92.     while(!qu.empty())
  93.     {
  94.         int u = qu.front();
  95.         qu.pop();
  96.         for(int v : ke[u])
  97.         {
  98.             if(dist[v] == -1)
  99.             {
  100.                 dist[v] = dist[u] + 1;
  101.                 qu.push(v);
  102.             }
  103.         }
  104.     }
  105. }
  106.  
  107. void sub1()
  108. {
  109.     for(int i = 1 ; i <= q ; i++)
  110.     {
  111.         if(qr[i].type == 1)
  112.         {
  113.             int x = qr[i].x , y = qr[i].y;
  114.             for(int u = 1 ; u <= n ; u++)
  115.             {
  116.                 for(int v = 1 ; v <= n ; v++)
  117.                 {
  118.                     if(u != v)
  119.                     {
  120.                         if((c[u] == x && c[v] == y) || (c[u] == y && c[v] == x)) ke[u].pb(v);
  121.                     }
  122.                 }
  123.             }
  124.         }
  125.         else
  126.         {
  127.             int u = qr[i].x , v = qr[i].y;
  128.             for(int j = 1 ; j <= n ; j++)
  129.             {
  130.                 if(c[j] == u) c[j] = v;
  131.             }
  132.         }
  133.     }
  134.  
  135.     bfs(1);
  136.     for(int i = 1 ; i <= n ; i++) cout << dist[i] << " ";
  137. }
  138.  
  139. vector<pii> ke2[3 * N];
  140. int dist2[3 * N];
  141.  
  142. void bfs01(int st)
  143. {
  144.     for(int i = 0 ; i < 3 * N ; i++) dist2[i] = INF;
  145.     deque<int> dq;
  146.  
  147.     dist2[st] = 0;
  148.     dq.push_front(st);
  149.  
  150.     while(!dq.empty())
  151.     {
  152.         int u = dq.front();
  153.         dq.pop_front();
  154.         for(auto edge : ke2[u])
  155.         {
  156.             int v = edge.fi , w = edge.se;
  157.             if(dist2[v] > dist2[u] + w)
  158.             {
  159.                 dist2[v] = dist2[u] + w;
  160.                 if(w == 0) dq.push_front(v);
  161.                 else dq.pb(v);
  162.             }
  163.         }
  164.     }
  165. }
  166.  
  167. void sub2()
  168. {
  169.     for(int i = 1 ; i <= n ; i++)
  170.     {
  171.         int in = n + c[i] , out = 2 * n + c[i];
  172.         ke2[in].pb({i , 0});
  173.         ke2[i].pb({out , 0});
  174.     }
  175.  
  176.     for(int i = 1 ; i <= q ; i++)
  177.     {
  178.         if(qr[i].type == 1)
  179.         {
  180.             int x = qr[i].x , y = qr[i].y;
  181.             ke2[2 * n + x].pb({n + y , 1});
  182.             ke2[2 * n + y].pb({n + x , 1});
  183.         }
  184.     }
  185.  
  186.     bfs01(1);
  187.     for(int i = 1 ; i <= n ; i++)
  188.     {
  189.         if(dist2[i] == INF) cout << -1 << " ";
  190.         else cout << dist2[i] << " ";
  191.     }
  192. }
  193.  
  194. void sub3()
  195. {
  196.     vector<vector<int>> lst(N);
  197.     for(int i = 1 ; i <= n ; i++) lst[c[i]].pb(i);
  198.  
  199.     for(int i = 1 ; i <= q ; i++)
  200.     {
  201.         if(qr[i].type == 2)
  202.         {
  203.             int u = qr[i].x , v = qr[i].y;
  204.             if(u == v || lst[u].empty()) continue;
  205.             if(lst[u].size() > lst[v].size()) lst[u].swap(lst[v]);
  206.             for(int node : lst[u]) lst[v].pb(node);
  207.             lst[u].clear();
  208.         }
  209.     }
  210.  
  211.     for(int col = 1 ; col < N ; col++)
  212.     {
  213.         for(int node : lst[col]) c[node] = col;
  214.     }
  215.     sub2();
  216. }
  217.  
  218. vector<pii> ke4[M];
  219. int dist4[M] , headn[N] , tailn[N];
  220. int ncnt;
  221.  
  222. void bfs01_sub4(int st)
  223. {
  224.     for(int i = 1 ; i <= ncnt ; i++) dist4[i] = INF;
  225.  
  226.     deque<int> dq;
  227.     dist4[st] = 0;
  228.     dq.push_front(st);
  229.  
  230.     while(!dq.empty())
  231.     {
  232.         int u = dq.front();
  233.         dq.pop_front();
  234.         for(auto edge : ke4[u])
  235.         {
  236.             int v = edge.fi , w = edge.se;
  237.             if(dist4[v] > dist4[u] + w)
  238.             {
  239.                 dist4[v] = dist4[u] + w;
  240.                 if(w == 0) dq.push_front(v);
  241.                 else dq.pb(v);
  242.             }
  243.         }
  244.     }
  245. }
  246.  
  247. void sub4()
  248. {
  249.     ncnt = n;
  250.     for(int i = 1 ; i <= n ; i++)
  251.     {
  252.         headn[i] = ++ncnt;
  253.         tailn[i] = ++ncnt;
  254.     }
  255.  
  256.     for(int i = 1 ; i <= n ; i++)
  257.     {
  258.         ke4[headn[c[i]]].pb({i, 0});
  259.         ke4[i].pb({tailn[c[i]], 0});
  260.     }
  261.  
  262.     for(int i = 1 ; i <= q ; i++)
  263.     {
  264.         if(qr[i].type == 1)
  265.         {
  266.             int x = qr[i].x, y = qr[i].y;
  267.             ke4[tailn[x]].pb({headn[y] , 1});
  268.             ke4[tailn[y]].pb({headn[x] , 1});
  269.         }
  270.         else
  271.         {
  272.             int x = qr[i].x , y = qr[i].y;
  273.             if(x == y) continue;
  274.  
  275.             int nwx = ++ncnt , ntx = ++ncnt;
  276.             int nhy = ++ncnt , nwy = ++ncnt;
  277.  
  278.             ke4[nhy].pb({headn[x], 0});
  279.             ke4[nhy].pb({headn[y], 0});
  280.  
  281.             ke4[tailn[x]].pb({nwy, 0});
  282.             ke4[tailn[y]].pb({nwy, 0});
  283.  
  284.             headn[x] = nwx;
  285.             tailn[x] = ntx;
  286.             headn[y] = nhy;
  287.             tailn[y] = nwy;
  288.         }
  289.     }
  290.  
  291.     bfs01_sub4(1);
  292.     for(int i = 1 ; i <= n ; i++)
  293.     {
  294.         if(dist4[i] == INF) cout << -1 << " ";
  295.         else cout << dist4[i] << " ";
  296.     }
  297. }
  298.  
  299. signed main()
  300. {
  301.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  302.     //IO
  303.  
  304.     cin >> n >> q;
  305.     for(int i = 1 ; i <= n ; i++) cin >> c[i];
  306.  
  307.     bool ok1 = true , check1 = false , ok2 = true;
  308.     for(int i = 1 ; i <= q ; i++)
  309.     {
  310.         cin >> qr[i].type >> qr[i].x >> qr[i].y;
  311.         if(qr[i].type == 1) check1 = true;
  312.         else
  313.         {
  314.             ok1 = false;
  315.             if(check1) ok2 = false;
  316.         }
  317.     }
  318.  
  319.     if(n <= 100 && q <= 100) sub1();
  320.     else if(ok1) sub2();
  321.     else if(ok2) sub3();
  322.     else sub4();
  323.  
  324.     return 0;
  325. }
  326.  
Success #stdin #stdout 0.02s 97768KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qFXgUs
language:
C++14 (clang 8.0)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!