P3471 [POI 2008] POC-Trains

The Trains of Colour Parade begins tomorrow in Byteotia. Intense preparations are already in progress at the station’s auxiliary tracks. There are $n$ parallel tracks at the station, numbered from $1$ to $n$. Train no. $i$ occupies the $i^{th}$ track. Every train consists of $l$ cars, and each car is painted with one of 26 colours (denoted by lowercase letters of the English alphabet). We say that two trains look the same if their corresponding cars are painted the same colour. Throughout the parade a crane will switch places of certain pairs of cars. The real parade, however, will take place tomorrow. Today the train dispatcher, Byteasar, watched the general rehearsal closely. He even wrote down the sequence of car swaps. Byteasar particularly dislikes many trains looking the same. For each train $p$ he would like to calculate the maximum number of trains that, at some moment, look the same as train $p$ at that very moment. Task Write a program that: - reads the descriptions of the trains occupying the tracks and the sequence of car swaps, - for each train determines the maximum number of trains that look the same as it at some moment, - writes out the result. Given $n$ strings, each of length $l$. There are $m$ operations, each swapping two characters. For each string, find the maximum number of strings that are identical to it at some moment.

The first line of input contains three integers $n$, $l$ and $m$ ($2 \le n \le 1000$, $1 \le l \le 100$, $0 \le m \le 100\,000$), denoting respectively the number of trains, their common length, and the number of car swaps. The following $n$ lines contain descriptions of the trains on successive tracks. The $k^{th}$ of these lines consists of $l$ lowercase letters of the English alphabet, denoting the colours of successive cars of the $k^{th}$ train. Then $m$ lines describing the car swaps follow, in the order of the swaps. The $r^{th}$ line contains four integers $p_1$, $w_1$, $p_2$, $w_2$ ($1 \le p_1, p_2 \le n$, $1 \le w_1, w_2 \le l$, $p_1 \ne p_2$ or $w_1 \ne w_2$), denoting the $r^{th}$ car swap—the car no. $w_1$ of train no. $p_1$ is swapped with the car no. $w_2$ of train no. $p_2$.

Your program should write out exactly $n$ lines. The $k^{th}$ line should contain one integer—the number of trains that, at some moment, look the same as train no. $k$.

The figure presents the successive car swaps: ```cpp track 1: ababbd ababbd ababbd ababbd aaabbd aaabbd aaabbd aaabbd track 2: abbbbd ababbd ababbd aaabbd aaabbd acabbd acabbd acabbd track 3: aaabad -> aaabad -> aaabad -> aaabbd -> aaabbd -> aaabbd -> aaabbd -> aaabbd track 4: caabbd caabbd caabbd caabbd cabbbd cabbbd cabbbd dabbbd track 5: cabaad cabbad caabbd caabbd caabbd aaabbd aaabbd aaabbc (0) (1) (2) (3) (4) (5) (6) (7) ``` The number of trains looking the same as either of trains no. 1, 2, or 3 was maximal at time (4) (when all three looked the same). The number of trains looking the same as train no. 5 was maximal at times (5) and (6). The number of trains looking the same as train no. 4 was maximal at time (2). Translated by ChatGPT 5