#P7298. [USACO21JAN] Dance Mooves G

[USACO21JAN] Dance Mooves G

题目描述

Farmer John 的奶牛们正在炫耀她们的最新舞步!

最初,所有的 NN 头奶牛(2N1052≤N≤10^5)站成一行,奶牛 ii 排在其中第 ii 位。舞步序列给定为 KK1K2×1051≤K≤2\times10^5)个位置对 (a1,b1),(a2,b2),,(aK,bK)(a_1,b_1),(a_2,b_2),…,(a_K,b_K)。在舞蹈的第 i=1Ki=1…K 分钟,位置 aia_ibib_i 上的奶牛交换位置。同样的 KK 次交换在第 K+12KK+1…2K 分钟发生,在第 2K+13K2K+1…3K 分钟再次发生,以此类推,周期性地持续共 MM 分钟(1M10181≤M≤10^{18})。换言之,

  • 在第 11 分钟,位置 a1a_1b1b_1 上的奶牛交换位置。
  • 在第 22 分钟,位置 a2a_2b2b_2 上的奶牛交换位置。
  • ……
  • 在第 KK 分钟,位置 aKa_KbKb_K 上的奶牛交换位置。
  • 在第 K+1K+1 分钟,位置 a1a_1b1b_1 上的奶牛交换位置。
  • 在第 K+2K+2 分钟,位置 a2a_2b2b_2 上的奶牛交换位置。
  • 以此类推……

对于每头奶牛,求她在队伍中会占据的不同的位置数量。

注意:本题每个测试点的时间限制为默认限制的两倍。

输入格式

输入的第一行包含 NNKKMM。以下 KK 行分别包含 (a1,b1)(aK,bK)(a_1,b_1)…(a_K,b_K)1ai<biN1≤a_i<b_i≤N)。

输出格式

输出 NN 行,第 ii 行包含奶牛 ii 可以到达的不同的位置数量。

6 4 7
1 2
2 3
3 4
4 5
5
4
3
3
3
1

提示

77 分钟之后,各个位置上的奶牛为 [3,4,5,2,1,6][3,4,5,2,1,6]

  • 奶牛 11 可以到达位置 {1,2,3,4,5}\{1,2,3,4,5\}
  • 奶牛 22 可以到达位置 {1,2,3,4}\{1,2,3,4\}
  • 奶牛 33 可以到达位置 {1,2,3}\{1,2,3\}
  • 奶牛 44 可以到达位置 {2,3,4}\{2,3,4\}
  • 奶牛 55 可以到达位置 {3,4,5}\{3,4,5\}
  • 奶牛 66 从未移动,所以她没有离开过位置 66

测试点性质:

  • 测试点 1-5 满足 N100,K200N≤100,K≤200
  • 测试点 6-10 满足 M=1018M=10^{18}
  • 测试点 11-20 没有额外限制。

Problem credits: Chris Zhang