Nell'informatica, i problemi NP-Completi (NP-Complete, abbreviati in NPC) costituiscono una classe di problemi classici che uniscono profondità teorica e difficoltà di risoluzione: finora non è stato trovato alcun algoritmo in tempo polinomiale per risolverli, ma non appena uno qualsiasi di essi verrà espugnato, tutti i problemi NP si risolveranno facilmente.
Il piccolo W, appassionato di ricerca algoritmica, ha sempre sognato di sfidare i problemi NPC. Ha scoperto che il celebre «Problema del massimo sottografo indotto comune» nella teoria dei grafi è proprio un classico problema NPC. Di fronte all'insormontabile divario di complessità sui grafi generali, il piccolo W ha deciso di fare un passo indietro e di partire dagli alberi, che possiedono una struttura più elegante, per studiare il problema dei sottografi connessi isomorfi sugli alberi.
Nello specifico, sono dati due alberi non radicati $T_1$ e $T_2$, ciascuno contenente $n$ nodi, con i nodi di entrambi gli alberi numerati rispettivamente da $1 \sim n$. Il piccolo W desidera selezionare un sottoinsieme non vuoto di nodi $V_1$ in $T_1$ e un sottoinsieme non vuoto di nodi $V_2$ in $T_2$, mantenendo tutti gli archi originali dell'albero di partenza tra i nodi interni a ciascun insieme, inducendo così rispettivamente due sottografi $G_1$ e $G_2$.
Il piccolo W richiede che i due sottografi indotti $G_1, G_2$ soddisfino contemporaneamente:
- Connettività: Sia $G_1$ che $G_2$ sono grafi connessi (in particolare, anche un grafo contenente solo $1$ nodo è considerato connesso).
- Isomorfismo: $G_1$ e $G_2$ sono isomorfi. Cioè esiste una biiezione (corrispondenza biunivoca) $f : V_1 \to V_2$ da $V_1$ a $V_2$ tale che, per ogni $u, v \in V_1$, $u$ e $v$ sono collegati da un arco in $G_1$ se e solo se $f(u)$ e $f(v)$ sono collegati da un arco in $G_2$. Nota: Non è richiesto che i nodi corrispondenti $u$ e $f(u)$ abbiano lo stesso indice.
Ora, il piccolo W affida a te questo problema semplificato: calcola quanti nodi al massimo possono contenere i sottografi connessi isomorfi che soddisfano i requisiti sopra indicati (ossia trova il valore massimo di $|V_1|$).
Dati di ingresso
Leggere i dati da stdin.
La prima riga contiene un intero positivo $n$, che rappresenta il numero di nodi di ciascun albero.
Le successive $n - 1$ righe contengono ciascuna due interi positivi $u, v$, che rappresentano un arco non orientato $(u, v)$ nell'albero $T_1$.
Le successive $n - 1$ righe contengono ciascuna due interi positivi $u, v$, che rappresentano un arco non orientato $(u, v)$ nell'albero $T_2$.
Dati di uscita
Scrivere il risultato su stdout.
Stampare una sola riga contenente un intero positivo, che rappresenta il numero massimo di nodi dei sottografi connessi isomorfi selezionati.
Esempi
Dati di ingresso 1
4 1 2 2 3 3 4 1 2 1 3 1 4
Dati di uscita 1
3
Spiegazione
Selezionando l'insieme di nodi $V_1 = \{1, 2, 3\}$ in $T_1$ e l'insieme di nodi $V_2 = \{1, 2, 3\}$ in $T_2$, e facendo corrispondere in ordine i nodi $1, 2, 3$ di $V_1$ ai nodi $2, 1, 3$ di $V_2$, i due sottografi indotti sono entrambi catene contenenti $3$ nodi, soddisfacendo sia la connettività sia l'isomorfismo.
Poiché $T_1$ stesso è una catena, qualsiasi suo sottografo connesso deve necessariamente essere una catena; d'altra parte, la catena più lunga nel grafo a stella $T_2$ contiene solo $3$ nodi, pertanto è impossibile selezionare sottografi connessi isomorfi con più di $3$ nodi.
Esempio 2
Vedere npc/npc2.in e npc/npc2.ans nella directory del concorrente.
Questo esempio soddisfa i vincoli del sottoproblema $1$.
Esempio 3
Vedere npc/npc3.in e npc/npc3.ans nella directory del concorrente.
Questo esempio soddisfa i vincoli del sottoproblema $4$.
Esempio 4
Vedere npc/npc4.in e npc/npc4.ans nella directory del concorrente.
Questo esempio soddisfa i vincoli del sottoproblema $7$.
Sottoproblemi
Per tutti i dati di test è garantito che $1 \le n \le 500$, gli indici di entrambi gli estremi di ciascun arco sono compresi tra $1 \sim n$, e i due grafi forniti sono alberi validi.
Il punteggio massimo di questo problema è di $150$ punti e viene utilizzata la valutazione a pacchetti per sottoproblemi. Si ottiene il punteggio di un sottoproblema solo superando tutti i casi di prova in esso contenuti. I limiti dettagliati per ciascun sottoproblema sono riportati nella tabella seguente.
| Sottoproblema | $n$ | Proprietà speciale | Punteggio |
|---|---|---|---|
| $1$ | $\le 10$ | Nessuna | $20$ |
| $2$ | $\le 60$ | Nessuna | $25$ |
| $3$ | $\le 100$ | Nessuna | $30$ |
| $4$ | $\le 500$ | A | $20$ |
| $5$ | $\le 500$ | B | $15$ |
| $6$ | $\le 500$ | C | $10$ |
| $7$ | $\le 500$ | Nessuna | $30$ |
Proprietà speciale A: Il grado di tutti i nodi in entrambi gli alberi non supera $3$.
Proprietà speciale B: Esiste una soluzione ottima la cui mappa di isomorfismo associa il nodo $1$ di $T_1$ al nodo $1$ di $T_2$.
Proprietà speciale C: È garantito che la risposta finale non sia inferiore a $n - 1$.
Nota: Il grado di un nodo in un albero indica il numero di archi direttamente collegati a quel nodo.