Farmer John’s Dancing Cows

Farmer John’s cows are showing off their new dance moves! Initially, the N cows (2\le N\le10^5) are standing in a line so that cow i is in the i^th position. A dance routine is given by a sequence of K (1\le K\le2\times10^5) swap operations: \((a_1,b_1),(a_2,b_2),\dots,(a_K,b_K)\). In minute i for i=1\ldots K the cows in positions a_i and b_i swap positions. Then the same K swaps repeat in minutes K+1\ldots2K, then in minutes 2K+1\ldots3K and so on, for a total of M minutes (1\le M\le10^{18}).

For each cow, determine the number of distinct positions it occupies over the course of the dance. Note that the initial position is counted, and the swaps occur exactly at the beginning of each minute.

Hint: The sequence of K swaps defines a permutation on positions. When the routine is repeated, cows follow cycles in this permutation. By simulating one full cycle (or the given M minutes when M<K), you can record, for each cow starting at position i, the set of positions reached. For M\ge K, group cows by the cycle in the permutation and then add the effect of a partial routine (if any).

All formulas are in LaTeX format.

inputFormat

The first line contains three integers N, K and M.

The following K lines each contain two integers a and b indicating that the cows in positions a and b swap positions.

outputFormat

Output N lines. The i^th line should contain a single integer: the number of distinct positions occupied by the cow that initially started in position i.

sample

3 2 1
1 2
2 3

2
2
1