Sherlock and Musical Notes
All submissions for this problem are available.Sherlock is a very talented musician. He is very fond of symmetric tunes and coins the term **hemidemisemiquaver** for it. A tune is a **hemidemisemiquaver** only if it gives the same sound when played from start to end or end to start. There are **N** notes provided to Sherlock and each note is represented by an integer. Sherlock is also provided **M** pairs of notes **a** and **b**, such that he can replace the note **a** with **b**. Sherlock is given a symphony **S** with **q** notes, and he is required to tell what is the maximum length of **hemidemisemiquaver** he can make from that tune. Please keep in mind, he is not allowed to change the sequence of notes. He can only replace notes from **M** pairs of interchangeable notes provided and then choose a subsequence. Transformations also have following additional properties: - If note **a** can be transformed to note **b** using a transformation, then note **b** can be transformed to note **a** as well. - If note **a** can be transformed to note **b** and note **b** can be transformed to note **c**, then note **a** can be transformed to note **c** as well. ###Input: • First line contains an integer **N** denoting the number of notes. • Second line contains an integer **M** denoting the number of transformations. • Each of the next **M** lines contain 2 space separated integers **a** and **b**, denoting a transformation from note **a** to note **b**. • After that, on a new line, an integer **q** denoting the number of elements in the symphony. • Next **q** lines contain positive integers denoting notes of the symphony. ###Output: Print an integer denoting the maximum length of **hemidemisemiquaver**. ###Constraints • $1 \leq N \leq 10^5$ • $1 \leq M \leq 10^6$ • $1 \leq a,b \leq N$ • $1 \leq q \leq 10^3$ • $1 \leq S[i] \leq N, for all 1 \leq i \leq q$ ###Sample Input: 10 7 1 3 5 7 3 5 2 6 2 4 8 4 10 9 6 1 9 2 3 10 3 ###Sample Output: 5 ###EXPLANATION: In the array **1 9 2 3 10 3**, we can substitute **1** with **3** and **9** with **10**. Thus, the array becomes **3 10 2 3 10 3**. Now, we can choose a subsequence **3 10 3 10 3** or **3 10 2 10 3** both of which are palindrome of length **5**. Hence, **5** is the output.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.