In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
The Trains of Colour Parade begins tomorrow in Byteotia. Intense preparations are already in progress at the station's auxiliary tracks. There are parallel tracks at the station, numbered from to . The train no. occupies the track. Every train consists of cars and each car is painted with one of 26 colours (denoted by non-capital 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 he would like to calculate the maximum number of trains that at some moment look the same as the train at the very same moment.
Write a programme that:
The first line of the input contains three integers , and (, , ), denoting respectively the number of trains, their common length and the number of car swaps. The following lines contain descriptions of the trains on successive tracks. The line consists of small letters of the English alphabet denoting the colours of successive cars of the train. Then lines describing the car swaps follow, in the order of the swaps. The line contains four integers , , , (, , or ) denoting the car swap-the car no. of the train no. is swapped with the car no. of the train no. .
Your programme should write out exactly lines. The line should contain one integer-the number of trains looking the same as the train no. at certain moment.
For the input data:
5 6 7 ababbd abbbbd aaabad caabbd cabaad 2 3 5 4 5 3 5 5 3 5 2 2 1 2 4 3 2 2 5 1 1 1 3 3 4 1 5 6
the correct result is:
3 3 3 2 3
The figure presents the successive car swaps:
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 the 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 the train no. 5 was maximal at time (5) and (6). The number of trains looking the same as the train no. 4 was maximal at time (2).
Task author: Piotr Stanczyk.