במדעי המחשב, בעיות NP-שלמות (NP-Complete, ובקיצור NPC) הן מחלקה של בעיות קלאסיות המשלבות עומק תאורטי וקושי חישובי — עד כה לא נמצא להן אלגוריתם בזמן פולינומי, אך ברגע שאחת מהבעיות הללו תיפתר, כל בעיות ה-NP ייפתרו בקלות.
W הקטן, הנלהב ממחקר אלגוריתמים, תמיד חלם לאתגר בעיות NPC. הוא למד ש"בעיית תת-הגרף המושרה המשותף המקסימלי" המפורסמת בתורת הגרפים היא בדיוק בעיית NPC קלאסית. מול פער הסיבוכיות הבלתי עביר בגרפים כלליים, החליט W הקטן לקחת צעד אחורה ולהתחיל מעצים, שלהם מבנה אלגנטי יותר, כדי לחקור את בעיית תתי-הגרפים הקשירים האיזומורפיים על עצים.
באופן ספציפי, נתונים שני עצים לא מכוונים וללא שורש $T_1$ ו-$T_2$, שכל אחד מהם מכיל $n$ צמתים הממוספרים בהתאמה מ-$1 \sim n$. W הקטן מעוניין לבחור תת-קבוצת צמתים לא ריקה $V_1$ ב-$T_1$ ותת-קבוצת צמתים לא ריקה $V_2$ ב-$T_2$, תוך שמירה על כל הקשתות המקוריות בעץ המקורי בין הצמתים בתוך כל קבוצה, ובכך להשרות בהתאמה שני תתי-גרפים $G_1$ ו-$G_2$.
W הקטן דורש ששני תתי-הגרפים המושרים $G_1, G_2$ יקיימו בו-זמנית:
- קשירות: גם $G_1$ וגם $G_2$ הם גרפים קשירים (בפרט, גם גרף המכיל צומת $1$ בלבד נחשב קשיר).
- איזומורפיזם: $G_1$ ו-$G_2$ איזומורפיים. כלומר, קיימת פונקציה חד-חד-ערכית ועל (התאמה חד-חד-ערכית) $f : V_1 \to V_2$ מ-$V_1$ ל-$V_2$, כך שלכל $u, v \in V_1$, בין $u$ ל-$v$ יש קשת ב-$G_1$ אם ורק אם בין $f(u)$ ל-$f(v)$ יש קשת ב-$G_2$. שימו לב: הצמתים המתאימים $u$ ו-$f(u)$ אינם חייבים להיות בעלי אותו מספר סידורי.
כעת, W הקטן מפקיד בידיך את הבעיה המפושטת הזו: חשב מהו מספר הצמתים המרבי שיכולים להכיל תתי-גרפים קשירים איזומורפיים המקיימים את הדרישות לעיל (כלומר, מצא את הערך המקסימלי של $|V_1|$)?
קלט
קרא את הנתונים מ-stdin.
השורה הראשונה מכילה מספר שלם חיובי $n$, המייצג את מספר הצמתים בכל עץ.
ב-$n - 1$ השורות הבאות, כל שורה מכילה שני מספרים שלמים חיוביים $u, v$, המייצגים קשת לא מכוונת $(u, v)$ בעץ $T_1$.
ב-$n - 1$ השורות הבאות, כל שורה מכילה שני מספרים שלמים חיוביים $u, v$, המייצגים קשת לא מכוונת $(u, v)$ בעץ $T_2$.
פלט
כתוב את הפלט ל-stdout.
הדפס שורה אחת המכילה מספר שלם חיובי אחד, המייצג את מספר הצמתים המרבי של תתי-הגרפים הקשירים האיזומורפיים שנבחרו.
דוגמאות
קלט 1
4 1 2 2 3 3 4 1 2 1 3 1 4
פלט 1
3
הסבר
נבחר ב-$T_1$ את קבוצת הצמתים $V_1 = \{1, 2, 3\}$, וב-$T_2$ את קבוצת הצמתים $V_2 = \{1, 2, 3\}$. אם נתאים את הצמתים $1, 2, 3$ ב-$V_1$ בהתאמה לצמתים $2, 1, 3$ ב-$V_2$, שני תתי-הגרפים המושרים הם שרשראות בנות $3$ צמתים, המקיימות קשירות ואיזומורפיזם.
מכיוון ש-$T_1$ עצמו הוא שרשרת, כל תת-גרף קשיר שלו חייב להיות גם הוא שרשרת; ואילו השרשרת הארוכה ביותר בגרף הכוכב $T_2$ מכילה $3$ צמתים בלבד, ולכן לא ניתן לבחור תתי-גרפים קשירים איזומורפיים עם יותר מ-$3$ צמתים.
דוגמה 2
ראו את הקבצים npc/npc2.in ו-npc/npc2.ans בתיקיית המתחרה.
דוגמה זו מקיימת את האילוצים של תת-משימה $1$.
דוגמה 3
ראו את הקבצים npc/npc3.in ו-npc/npc3.ans בתיקיית המתחרה.
דוגמה זו מקיימת את האילוצים של תת-משימה $4$.
דוגמה 4
ראו את הקבצים npc/npc4.in ו-npc/npc4.ans בתיקיית המתחרה.
דוגמה זו מקיימת את האילוצים של תת-משימה $7$.
תתי-משימות
עבור כל הנתונים, מובטח כי $1 \le n \le 500$, מספרי שתי נקודות הקצה של כל קשת נמצאים בטווח $1 \sim n$, ושני הגרפים הנתונים הם עצים חוקיים.
הציון המלא עבור בעיה זו הוא $150$ נקודות, ונעשה שימוש בבדיקה מקובצת לפי תתי-משימות. תקבל את הניקוד של תת-משימה רק אם תעבור את כל מקרי הבדיקה באותה תת-משימה. טווחי הנתונים המפורטים לכל תת-משימה מוצגים בטבלה שלהלן.
| מספר תת-משימה | $n$ | תכונה מיוחדת | ניקוד |
|---|---|---|---|
| $1$ | $\le 10$ | ללא | $20$ |
| $2$ | $\le 60$ | ללא | $25$ |
| $3$ | $\le 100$ | ללא | $30$ |
| $4$ | $\le 500$ | A | $20$ |
| $5$ | $\le 500$ | B | $15$ |
| $6$ | $\le 500$ | C | $10$ |
| $7$ | $\le 500$ | ללא | $30$ |
תכונה מיוחדת A: הדרגה של כל הצמתים בשני העצים אינה עולה על $3$.
תכונה מיוחדת B: קיים פתרון אופטימלי שהעתקת האיזומורפיזם שלו מתאימה את צומת $1$ של $T_1$ לצומת $1$ של $T_2$.
תכונה מיוחדת C: מובטח שהתשובה הסופית אינה קטנה מ-$n - 1$.
הערה: הדרגה של צומת בעץ היא מספר הקשתות המחוברות ישירות לאותו צומת.