== include(page="template/taskheader" task_id="wildcards") ==

Numim *pattern* un sir nevid format doar din caracterele $0$, $1$ si $?$. Spunem că două patternuri $A$ si $B$ de
aceeai lungime se potrivesc daca si numai daca caracterele $?$ pot fi ı̂nlocuite convenabil cu $0$ si $1$ astfel incat cele două siruri să devină identice. De exemplu, pentru $A = “110?1”$, $B = “1?001”, C = “??1?1”$,
sirurile A si B se potrivesc (se poate forma sirul “11001” prin inlocuirea semnelor de intrebare cu valori),

Numim *pattern* un sir *nevid* format doar din caracterele $0$, $1$ si $?$. Spunem că două patternuri $A$ si $B$ de aceeasi lungime *se potrivesc* daca si numai daca caracterele $?$ pot fi ı̂nlocuite convenabil cu $0$ si $1$ astfel incat cele două siruri să devină identice. De exemplu, pentru $A = “110?1”$, $B = “1?001”, C = “??1?1”$, sirurile $A$ si $B$ se potrivesc (se poate forma sirul $“11001”$ prin inlocuirea semnelor de intrebare cu valori),

dar sirurile $A$ si $C$ nu se potrivesc.

Se da un arbore (graf neorientat conex aciclic) cu $N$ noduri. Se cere să se atribuie fiecărui nod câte un
sir format din caracterele $0$, $1$ si $?$ (un pattern) astfel incat să se respecte următoarele proprietati:
 
 * Toate patternurile sa aiba aceeasi lungime, care să fie cat mai mica (a se vedea rubrica *Punctare*).
 * Pentru oricare două noduri distincte $u$ si $v$, patternurile asociate acestora se potrivesc dacă si
numai dacă există muchia $(u, v)$ ı̂n arbore.
 
 

h2. Date de intrare
Fişierul de intrare $wildcards.in$ ...